| Description |
1 online resource (xiii, 311 pages) |
| Contents |
Cover -- Contents -- Preface -- Part I58; Background and Theory -- 1 Introduction -- 146;1 Bandersnatch Design -- 146;2 Informal Background -- 146;3 Some History -- 146;4 Related Works -- 146;5 Overview of This Book -- 2 Parallel Models of Computation -- 1 Introduction -- 2 The PRAM Model -- 3 The Boolean Circuit Model -- 4 Circuits and PRAMs -- 3 Complexity -- 346;1 Search and Decision Problems -- 346;2 Complexity Classes -- 346;3 Reducibility -- 346;4 Other NC Compatible Reducibilities -- 346;5 Completeness -- 4 Two Basic P45;Complete Problems -- 446;1 The Generic P45;Complete Problem -- 446;2 The Circuit Value Problem -- 5 Evidence That NC Does Not Equal P -- 546;1 Introduction -- 546;2 General Simulations Are Not Fast -- 546;3 Fast Simulations Are Not General -- 546;4 Natural Approaches Provably Fail -- 546;5 Summary -- 6 The Circuit Value Problem -- 646;1 The Circuit Value Problem Is P45;Complete -- 646;2 Restricted Versions of Cimiit Value -- 7 Greedy Algorithms -- 746;1 Lexicographic Greedy Algorithms -- 746;2 Generic Greedy Algorithms -- 8 P45;Complete Algorithms -- 846;1 Introduction -- 846;2 Inherently Sequential Algorithms -- 846;3 Applications of the Model -- 9 Two Other Notions of P45;Completeness -- 946;1 Strong P45;Completeness -- 946;2 Strict P45;Completeness -- 10 Approximating P45;Complete Problems -- 1046;1 Introduction -- 1046;2 Approximating LFMIS Is Hard -- 1046;3 Approximation Schemes -- 11 Closing Remarks -- Part II58; A Compendium of Problems -- A58; P45;Complete Problems -- A46;1 Circuit Complexity -- A46;2 Graph Theory -- A46;3 Searching Graphs -- A46;4 Combinatorial Optimization -- A46;5 Local Optimality -- A46;6 Logic -- A46;7 Formal Languages -- A46;8 Algebra -- A46;9 Geometry -- A46;10 Real Analysis -- A46;11 Games -- A46;12 Miscellaneous -- B58; Open Problems -- B46;1 Graph Theory -- B46;2 Combinatorial Optimization -- B46;3 Logic -- B46;4 Formal Languages -- B46;5 Algebra -- B46;6 Geometry -- B46;7 Real Analysis -- B46;8 CC -- B46;9 RNC -- C58; Notation -- D58; Complexity Classes -- D46;1 Definitions -- D46;2 Relationships Among Complexity Classes -- Bibliography -- Problem List -- Index -- A -- B -- C -- D -- E -- F -- G -- H -- I -- J -- K -- L -- M -- N -- O -- P -- Q -- R -- S -- T -- U -- V -- W -- Y -- Z -- Last Page |
| Summary |
This volume provides an ideal introduction to key topics in parallel computing. With its cogent overview of the essentials of the subject as well as lists of P -complete- and open problems, extensive remarks corresponding to each problem, a thorough index, and extensive references, the book will prove invaluable to programmers stuck on problems that are particularly difficult to parallelize. In providing an up-to-date survey of parallel computing research from 1994, Topics in Parallel Computing will prove invaluable to researchers and professionals with an interest in the super computers of the future |
| Analysis |
Parallel programming |
| Bibliography |
Includes bibliographical references (pages 255-284) and index |
| Notes |
Print version record |
| Subject |
Parallel processing (Electronic computers)
|
|
COMPUTERS -- Systems Architecture -- Distributed Systems & Computing.
|
|
Parallel processing (Electronic computers)
|
| Form |
Electronic book
|
| Author |
Hoover, H. James
|
|
Ruzzo, Walter L
|
| LC no. |
94031180 |
| ISBN |
1429406429 |
|
9781429406420 |
|
1280540036 |
|
9781280540035 |
|
