Download PDF by Ruy Luiz Milidiú, Artur Alves Pessoa, Eduardo Sany Laber: Algorithm Engineering and Experimentation: International

By Ruy Luiz Milidiú, Artur Alves Pessoa, Eduardo Sany Laber (auth.), Michael T. Goodrich, Catherine C. McGeoch (eds.)

ISBN-10: 354048518X

ISBN-13: 9783540485186

ISBN-10: 3540662278

ISBN-13: 9783540662273

Symmetric multiprocessors (SMPs) dominate the high-end server industry and are at the moment the first candidate for developing huge scale multiprocessor structures. but, the layout of e cient parallel algorithms for this platform c- rently poses numerous demanding situations. this is why the speedy growth in microprocessor velocity has left major reminiscence entry because the fundamental obstacle to SMP functionality. given that reminiscence is the bottleneck, easily expanding the n- ber of processors won't unavoidably yield greater functionality. certainly, reminiscence bus barriers as a rule restrict the scale of SMPs to sixteen processors. This has no less than twoimplicationsfor the algorithmdesigner. First, considering the fact that there are quite few processors availableon an SMP, any parallel set of rules needs to be aggressive with its sequential counterpart with as low as one processor with the intention to be r- evant. moment, for the parallel set of rules to scale with the variety of processors, it has to be designed with cautious consciousness to minimizing the quantity and kind of major reminiscence accesses. during this paper, we current a computational version for designing e cient al- rithms for symmetric multiprocessors. We then use this version to create e cient ideas to 2 broadly di erent varieties of difficulties - associated record pre x com- tations and generalized sorting. either difficulties are reminiscence in depth, yet in die hire methods. while generalized sorting algorithms in most cases require a wide numberofmemoryaccesses, they areusuallytocontiguousmemorylocations. against this, prex computation algorithms ordinarily require a extra modest qu- tity of reminiscence accesses, yet they're are typically to non-contiguous reminiscence locations.

Show description

Read Online or Download Algorithm Engineering and Experimentation: International Workshop ALENEX’99 Baltimore, MD, USA, January 15–16, 1999 Selected Papers PDF

Similar engineering books

Impact Engineering of Composite Structures by Serge Abrate (auth.), Serge Abrate (eds.) PDF

The e-book offers an creation to the mechanics of composite fabrics, written for graduate scholars and practitioners in undefined. It examines how you can version the impression occasion, to figure out the scale and severity of the wear and tear and discusses basic tendencies saw in the course of experiments.

Get Algorithm Engineering and Experimentation: International PDF

Symmetric multiprocessors (SMPs) dominate the high-end server marketplace and are presently the first candidate for developing huge scale multiprocessor platforms. but, the layout of e cient parallel algorithms for this platform c- rently poses a number of demanding situations. this is because the quick development in microprocessor velocity has left major reminiscence entry because the basic challenge to SMP functionality.

Extra info for Algorithm Engineering and Experimentation: International Workshop ALENEX’99 Baltimore, MD, USA, January 15–16, 1999 Selected Papers

Example text

R. Helman, J. J´ aJ´ a must contend with the extreme simplicity of the obvious sequential solution. A prefix computation can be performed by a single processor with two passes through the list, the first to identify the head of the list and the second to compute the prefix values. The pseudocode for this obvious sequential algorithm is as follows: – (1): Visit each list element Xi in order of ascending array index. succ as having a predecessor. – (2): Find the one element not labeled as having a predecessor by visiting each list element Xi in order of ascending array index - this unlabeled element is the head of the list.

Corresponding to each of these sublists is a record in an array called Sublists. We then traverse each of these sublists, making a note at each list element of the index of its sublist and the prefix value of that element within the sublist. The results of these sublist traversals are also used to create a linked list of the records in Sublists, where the input value of each node is simply the sublist prefix value of the last element in the previous sublist. We then determine the prefix values of the records in the Sublists array by sequentially traversing this list from its head.

2): Beginning at the head, traverse the elements in the list by following the successor pointers. For each element traversed with index i and predecessor pre, set List[i]. prefix data. Since this modified algorithm requires no more than approximately n noncontiguous memory accesses while running in O(n) computation time, it is optimal according to our model. Designing Practical Efficient Algorithms 43 The first fast parallel algorithm for prefix computations was probably the list ranking algorithm of Wyllie [18], which requires at least n log n non-contiguous accesses.

Download PDF sample

Algorithm Engineering and Experimentation: International Workshop ALENEX’99 Baltimore, MD, USA, January 15–16, 1999 Selected Papers by Ruy Luiz Milidiú, Artur Alves Pessoa, Eduardo Sany Laber (auth.), Michael T. Goodrich, Catherine C. McGeoch (eds.)


by Kenneth
4.4

Rated 4.62 of 5 – based on 35 votes