41033149
Parallel Restructuring and Evaluation of Expressions
Abstract In this paper we describe a boolean network of size O ( N 2 log N ) which accepts a fully parenthesized N -variable expression over a given semiring and produces its value in O (log N ) time. The network consists of two components: a preprocessor and a universal evaluator. The preprocessor computes the destinations of the expression terms and routes them to the correct input terminals of the universal evaluator.
18686062
Sequencing-by-hybridization revisited: the analog-spectrum proposal
All published approaches to DNA sequencing by hybridization (SBH) consist of the biochemical acquisition of the spectrum of a target sequence (the set of its subsequences conforming to a given probing pattern) followed by the algorithmic reconstruction of the sequence from its spectrum. In the "standard" or "uniform" approach, the probing pattern is a string of length L and the length of reliably reconstructible sequences is known to be m/sub len/ = O(2/sup L/). For a fixed microarray area, higher sequencing performance can be achieved by inserting nonprobing gaps ("wild-cards") in the probing pattern. The reconstruction, however, must cope with the emergence of fooling probes due to the gaps and algorithmic failure occurs when the spectrum becomes too densely populated, although we can achieve m/sub comp/ = O(4/sup L/). Despite the combinatorial success of gapped probing, all current approaches are based on a biochemically unrealistic spectrum-acquisition model (digital-spectrum). The reality of hybridization is much more complex. Departing from the conventional model, in this paper, we propose an alternative, called the analog-spectrum model, which more closely reflects the biochemical process. This novel modeling reestablishes probe length as the performance-governing factor, adopting "semidegenerate bases" as suitable emulators of currently inadequate universal bases. One important conclusion is that accurate biochemical measurements are pivotal to the success of SBH. The theoretical proposal presented in this paper should be a convincing stimulus for the needed biotechnological work.
37382391
Horizons of Parallel Computation
This paper considers the ultimate impact of fundamental physical limitations---notably, speed of light and device size---on parallel computing machines. Although we fully expect an innovative and very gradual evolution to the limiting situation, here we take the provocative view of exploring the consequences of the accomplished attainment of the physical bounds. The main result is that scalability holds only for neighborly interconnections, such as the square mesh, of bounded-size synchronous modules, presumably of the area-universal type. We also discuss the ultimate infeasibility of latency-hiding, the violation of intuitive maximal speedups, and the emerging novel processor-time tradeoffs.
45504051
Horizons of Parallel Computation
This paper considers the ultimate impact of fundamental physical limitations—notably, speed of light and device size—on parallel computing machines. Although we fully expect an innovative and very gradual evolution to the limiting situation, we take here the provocative view of exploring the consequences of the accomplished attainment of the physical bounds. The main result is that scalability holds only for neighborly interconnections, such as the square mesh, of bounded-size synchronous modules, presumably of the area-universal type. We also discuss the ultimate infeasibility of latency-hiding, the violation of intuitive maximal speedups, and the emerging novel processor-time tradeoffs.
62245037
Processor—Time Tradeoffs under Bounded-Speed Message Propagation: Part I, Upper Bounds
Upper bounds are derived for the processor—time tradeoffs of machines such as linear arrays and two-dimensional meshes, which are compatible with the physical limitation expressed by bounded-speed propagation of messages (due to the finiteness of the speed of light). It is shown that parallelism and locality combined may yield speedups superlinear in the number of processors. The speedups are inherent, due to the optimality of the obtained tradeoffs as established in a companion paper.Simulations of multiprocessor machines are developed by analogous machines with fewer processors. A crucial role is played by the hierarchical nature of the memory system. A divide-and-conquer technique for hierarchical memories is developed, based on the graph-theoretic notion of a topological separator. For multiprocessors, this technique also requires a careful balance of memory access and interprocessor communication costs, which leads to nonintuitive orchestrations of the simulation process.
1952504
Data structures and algorithms for the string statistics problem
Given a textstringx of lengthn, theMinimal Augmented Suffix Tree T (x) ofx is a digital-search index that returns, for anyquery stringw and in a number of comparisons bounded by the length ofw, the maximum number of nonoverlapping occurrences ofw inx. It is shown that, denoting the length ofx byn, T(x) can be built in timeO(n log2n) and spaceO(n logn), off-line on a RAM.
39821605
Area-Time Optimal VLSI Networks for Multiplying Matrices
206621028
Efficient Parallel Evaluation of Boolean Expressions
A Boolean expression wilth n literals, i.e., n distinct appearances of variables, can be evaluated by a parallel processing system in at most 1.81 log2n steps, or, equivalently, by a network constructed with two-input AND and OR gates and having at most 1.81 log2n levels.
15570871
Restructuring of Arithmetic Expressions For Parallel Evaluation
Let <italic>E</italic> be an arithmetic expression involving <italic>n</italic> variables, each of which appears just once, and the possible operations of addition, multiplication, and division. Although other cases are considered, when these three operations take unit time the restructuring algorithms presented in this paper yield evaluation times no greater than 2.88 log<subscrpt>2</subscrpt><italic>n</italic> + 1 and 2.08 log<subscrpt>2</subscrpt><italic>n</italic> for general expressions and division-free expressions, respectively. The coefficients are precisely given by 2/log<subscrpt>2</subscrpt>α ≈ 2.88 and 1/log<subscrpt>2</subscrpt><italic>β</italic> ≈ 2.08, where <italic>α</italic> and <italic>β</italic> are the positive real roots of the equations <italic>z</italic><supscrpt>2</supscrpt> = <italic>z</italic> + 1 and <italic>z</italic><supscrpt>4</supscrpt> = 2<italic>z</italic> + 1, respectively. While these times were known to be of order log<subscrpt>2</subscrpt><italic>n</italic>, the best previously known coefficients were 4 and 2.15 for the two cases.
The authors conjecture that the present coefficients are the best possible, since they have exhibited expressions which seem to require these times within an additive constant.
The paper also gives upper bounds to the restructuring time of a given expression <italic>E</italic> and to the number of processors required for its parallel evaluation. It is shown that at most <italic>O</italic><italic>(n</italic><supscrpt>1.44</supscrpt><italic>)</italic> and <italic>O</italic>(n<supscrpt>1.82</supscrpt><italic>)</italic> operations are needed for restructuring general expressions and division-free expression, respectively.
  It is pointed out that, since the order of the compiling time is greater than <italic>n</italic> log <italic>n</italic>, the numbers of required processors exhibit the same rate of growth in <italic>n</italic> as the corresponding compiling times.
5027597
Structural Properties of the String Statistics Problem
Abstract A suitably weighted Index Tree such as a B-tree or a Suffix Tree can be easily adapted to store, for a given string x and for all substrings w of x , the number of distinct instances of w along x . The storage needed is seen to be linear in the length of x : moreover, the whole statistics can itself be derived in linear time, off-line of a RAM. If the substring w has nontrivial periods, however, the number of distinct instances might differ from that of distinct non-overlapping occurrences along x . It is shown here that O ( n log n ) storage units— n standing for the length of x —are sufficient to organize this second kind of statistics, in such a way that the maximum number of nonoverlapping instances for arbitrary w along x can be retrieved in a number of character comparisons not exceeding the length of w .
13915150
Deterministic P-RAM simulation with constant redundancy
In this paper, we show that distributing the memory of a parallel computer and, thereby, decreasing its granularity allows a reduction in the redundancy required to achieve polylog simulation time for each PRAM step. Previously, realistic models of parallel computation assigned one memory module to each processor and, as a result, insisted on relatively coarse-grain memory. We propose, on the other hand, a more flexible, but equally valid model of computation, the distributed-memory, bounded-degree network (DMBDN) model. This model allows the use of fine-grain memory while maintaining the realism of a bounded-degree interconnection network. We describe a P-RAM simulation scheme, which is admitted under the DMBDN model, that exploits the increased memory bandwidth provided by a two-dimensional mesh of trees (2DMOT) network to achieve an overhead in memory redundancy lower than that required by other fast, deterministic P-RAM simulations. Specifically, for a deterministic simulation of an n-processor P-RAM on a bounded-degree network, we are able to reduce the number of copies of each variable from O(logn/loglogn) to ®(1) and still simulate each P-RAM step in polylog time.