LEADER 06117nam 22008415 450 001 9910767572103321 005 20250730104840.0 010 $a3-540-48318-7 024 7 $a10.1007/3-540-48318-7 035 $a(CKB)1000000000211188 035 $a(SSID)ssj0000321160 035 $a(PQKBManifestationID)11246316 035 $a(PQKBTitleCode)TC0000321160 035 $a(PQKBWorkID)10260431 035 $a(PQKB)10409745 035 $a(DE-He213)978-3-540-48318-2 035 $a(MiAaPQ)EBC3072213 035 $a(MiAaPQ)EBC6485772 035 $a(PPN)155215418 035 $a(BIP)6146151 035 $a(EXLCZ)991000000000211188 100 $a20121227d1999 u| 0 101 0 $aeng 135 $aurnn#008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aAlgorithm Engineering $e3rd International Workshop, WAE'99 London, UK, July 19-21, 1999 Proceedings /$fedited by Jeffrey S. Vitter, Christos D. Zaroliagis 205 $a1st ed. 1999. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d1999. 215 $a1 online resource (VIII, 368 p.) 225 1 $aLecture Notes in Computer Science,$x1611-3349 ;$v1668 300 $a"This volume contains the papers accepted for presentation at the 3rd International Workshop on Algorithm Engineering (WAE'99) held in London, UK, on July 19-21, 1999"--Introd. 311 08$a3-540-66427-0 320 $aIncludes bibliographical references and index. 327 $aInvited Lectures -- Selecting Problems for Algorithm Evaluation -- BSP Algorithms ? ?Write Once, Run Anywhere? -- Ten Years of LEDA: Some Thoughts -- Contributed Papers -- Computing the K Shortest Paths: A New Algorithm and an Experimental Comparison -- Efficient Implementation of Lazy Suffix Trees -- Experiments with List Ranking for Explicit Multi-Threaded (XMT) Instruction Parallelism -- Finding Minimum Congestion Spanning Trees -- Evaluation of an Algorithm for the Transversal Hypergraph Problem -- Construction Heuristics and Domination Analysis for the Asymmetric TSP -- Counting in Mobile Networks: Theory and Experimentation -- Dijkstra?s Algorithm On-Line: An Empirical Case Study from Public Railroad Transport -- Implementation and Experimental Evaluation of Graph Connectivity Algorithms Using LEDA -- On-Line Zone Construction in Arrangements of Lines in the Plane -- The Design and Implementation of Planar Maps in CGAL -- An Easy to Use Implementation of Linear Perturbations within Cupgal -- Analysing Cache Effects in Distribution Sorting -- Fast Regular Expression Search -- An Experimental Evaluation of Hybrid Data Structures for Searching -- LEDA-SM: Extending LEDA to Secondary Memory -- A Priority Queue Transform -- Implementation Issues and Experimental Study of a Wavelength Routing Algorithm for Irregular All-Optical Networks -- Estimating Large Distances in Phylogenetic Reconstruction -- The Performance of Concurrent Red-Black Tree Algorithms -- Performance Engineering Case Study: Heap Construction -- A Fast and Simple Local Search for Graph Coloring -- BALL: Biochemical Algorithms Library -- An Experimental Study of Priority Queues in External Memory. 330 $aThis work considers practical parallel list-ranking algorithms. The model for which programs are written is a single-program multiple-data (SPMD) \bri- ingmodel". Thismodel isdesignated asa programmer'smodelfora ne-grained computation framework called Explicit Multi-Threading (XMT), which was - troduced in [VDBN98]; the XMT framework covers the spectrum from al- rithms through architecture to implementation; it is meant to provide a pl- form for faster single-task completion time by way of instruction-level par- lelism (ILP). The performance of XMT programs is evaluated as follow: the performance of a matching optimized XMT assembly code is measured within an XMT execution model. (We use in the current paper the so-called Spawn- MT programmingmodel - the easier to implement amongthe two programming modelspresented in[VDBN98]). The XMT approach deviatesfromthe standard PRAM approach by incorporating reduced synchrony and departing from the lock-step structure in its so-called asynchronous mode. Our envisioned platform uses an extension to a standard serial instruction set. This extension e ciently implements PRAM-style algorithms using explicit multi-threaded ILP, which allows considerably more n e-grained parallelism than the previously studied parallel computing implementation platforms/models. The list ranking problem was the rst problem considered as we examined and re ned many of the concepts in the XMT framework. The problem arises in parallel algorithmson lists, trees and graphs and is considered a fundamental problemin the theory of parallelalgorithms. Experimental results are presented. 410 0$aLecture Notes in Computer Science,$x1611-3349 ;$v1668 606 $aComputer programming 606 $aComputer science 606 $aAlgorithms 606 $aNumerical analysis 606 $aComputer networks 606 $aDiscrete mathematics 606 $aProgramming Techniques 606 $aTheory of Computation 606 $aAlgorithms 606 $aNumerical Analysis 606 $aComputer Communication Networks 606 $aDiscrete Mathematics 615 0$aComputer programming. 615 0$aComputer science. 615 0$aAlgorithms. 615 0$aNumerical analysis. 615 0$aComputer networks. 615 0$aDiscrete mathematics. 615 14$aProgramming Techniques. 615 24$aTheory of Computation. 615 24$aAlgorithms. 615 24$aNumerical Analysis. 615 24$aComputer Communication Networks. 615 24$aDiscrete Mathematics. 676 $a005.1 702 $aZaroliagis$b Christos D.$f1963- 702 $aVitter$b Jeffrey S.$f1955- 712 12$aInternational Workshop on Algorithm Engineering. 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910767572103321 996 $aAlgorithm engineering$91980326 997 $aUNINA