1,721,024 research outputs found
A new scheme for the deterministic simulation of PRAMs in VLSI
No full textA deterministic scheme for the simulation of (n, m)-PRAM computation is devised. Each PRAM step is simulated on a bounded degree network consisting of a mesh-of-trees (MT) of siden. The memory is subdivided inn modules, each local to a PRAM processor. The roots of the MT contain these processors and the memory modules, while the otherO(n 2) nodes have the mere capabilities of packet switchers and one-bit comparators. The simulation algorithm makes a crucial use of pipelining on the MT, and attains a time complexity ofO(log2 n/log logn). The best previous time bound wasO(log2 n) on a different interconnection network withn processors. While the previous simulation schemes use an intermediate MPC model, which is in turn simulated on a bounded degree network, our method performs the simulation directly with a simple algorithm
Network Decontamination in Presence of Local Immunity
No full textWe consider the problem of decontaminating a network infected by a mobile virus. The goal is to perform the task using as small a team of antiviral agents as possible, avoiding recontamination of disinfected areas. In all the existing literature, it is assumed that the immunity level of a decontaminated site is nil; that is, a decontaminated node, in absence of an antiviral agent on site, may be re-contaminated by any infected neighbour. The network decontamination problem is studied here under a new model of immunity to recontamination: we consider the case when a decontaminated vertex, after the cleaning agent has gone, will become recontaminated only if a majority of its neighbours are infected. We study the impact that the presence of local immunity has on the number of antiviral agents necessary to decontaminate the entire network. We establish both lower and upper bounds on the number cleaners in the case of (multidimensional) toroidal meshes, graphs of vertex degree at most three (e.g., cubic graphs, binary trees, etc.), and of tree networks. In all cases the established bounds are tight. All upper-bound proofs are constructive; i.e., we exhibit decontamination protocol achieving the claimed bound. We also analyze the total number of moves performed by the agents, and establish tight bounds in some cases
Synthesis of integer multipliers in sum of pseudoproducts form
No full textWe discuss the realization of two standard multiplier structures in a three-level form based on EXOR, called sum of pseudoproducts (SPP for short). SPP extends the classical two-level sum of products form (SOP). Our study focuses on the minimization of the number of gates and levels of the circuits needed to construct Wallace-type multipliers, and a 54 × 54-bit multiplier. The basic building blocks explicitly studied are the 4 × 4 parallel multiply module, and the family of carry-save adders Ci, with i input lines, that compose the Wallace trees. We show that the ratio of the number of gates of Ci in SPP over SOP decreases exponentially with i, being very small even for small values of i (ratio > 0.2 for i = 9). The evaluation of power, speed, and chip area with three different standard tools also shows the interest of the proposed approach
Network Decontamination with local immunization
Full text linkWe consider the problem of decontaminating a network infected by a mobile virus. The goal is to perform, the task using as small a team of antiviral agents, avoiding any recontamination of disinfected areas, and minimizing the amount of agents' movements across the network. In all the existing literature, it is assumed that the immunity level of a disinfected site is nil. In this paper we consider the network decontamination problem under a new model of immunity to recontamination: we consider the case when a disinfected vertex, after the cleaning agent has gone, will become recontaminated only if a weak majority of its neighbours are infected. We study the effects of this level of immunity on the number of antiviral agents necessary to decontaminate the entire network. We focus on tori and on trees, and establish lower-bounds on the team size; we also establish lower bounds on the number of moves performed by an optimal-size time of cleaners. We design and present strategies for disinfecting tori and trees; we prove that these strategies are optimal in terms of both team size and number of moves. In particular, the upper and lower bounds are are tight for tree networks and for synchronous tori; the bounds are within a constant factor of each other in the case of asynchronous tori
Exploiting regularities for boolean function synthesis
No full textThe "regularity" of a Boolean function can be exploited for decreasing its minimization time. It has already been shown that the notion of autosymmetry is a valid measure of regularity, however such a notion has been studied thus far either in the theoretical framework of self-dual Boolean functions, or for the synthesis of a particular family of three-level logic networks. In this paper we show that the degree of autosymmetry of an arbitrary function can be computed implicitly in a very efficient way, and autosymmetry can then be exploited in any logic minimization context. Our algorithms make crucial use of Binary Decision Diagrams. A set of experimental results on the synthesis of standard benchmark functions substantiates the practical relevance of our theoretical results
Implicit Test of Regularity for Incompletely Specified Boolean Functions
No full textThe 'regularity' of a Boolean function can be exploited to
decrease its minimization time. In particular, a recent paper
shows that the notion of autosymmetry is a valid measure
of regularity. Autosymmetric functions have been studied in a
tree-level logic framework. In this paper we propose the exploiting
of autosimmetry in any logic minimization contest.
The aim of this paper is twofold: we extend the notion
of autosymmetry to not completely specified Boolean functions,
and we propose an implicit autosimmetry test algorithm
- …
