Name
Abstract | ||
|---|---|---|
A data-accumulating algorithm (d-algorithm for short) works on an input considered as a virtually endless stream. The computation terminates when all the currently arrived data have been processed before another datum arrives. In this paper, the class of d-algorithms is characterized. It is shown that this class is identical to the class of on-line algorithms. The parallel implementation of d-algorithms is then investigated. It is found that, in general, the speedup achieved through parallelism can be made arbitrarily large for almost any such algorithm. On the other hand, we prove that for d-algorithms whose static counterparts manifest only unitary speedup, no improvement is possible through parallel implementation. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1007/s002249910005 | Theory of Computing Systems \/ Mathematical Systems Theory |
Keywords | Field | DocType |
static counterpart,parallel implementation,computation terminates,on-line algorithm,data-accumulating algorithms,data-accumulating algorithm,endless stream,unitary speedup,data engineering,shape,information science,real time,parallel algorithms,turing machines,concurrent computing | Analysis of parallel algorithms,Combinatorics,Computer science,Parallel algorithm,Algorithm,Super-recursive algorithm,Linear speedup theorem,Arbitrarily large,Cost efficiency,Computation,Speedup | Journal |
Volume | Issue | ISSN |
33 | 1 | 1432-4350 |
ISBN | Citations | PageRank |
0-7695-0143-5 | 7 | 0.69 |
References | Authors | |
8 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stefan D. Bruda | 1 | 62 | 12.18 |
| Selim G. Akl | 2 | 2074 | 299.32 |