Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques
Uzi Vishkin · 2008
Contents 1 Preface - A Case for Studying Parallel Algorithms 4 1.1 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 1.2 More background and detail : : : : : : : : : : : : : : : : : : : : : : : : : 6 2 Introduction 8 2.1 The PRAM Model : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8 2.1.1 Example of a PRAM algorithm : : : : : : : : : : : : : : : : : : : 9 2.2 Data-Parallel presentation of algorithms : : : : : : : : : : : : : : : : : : 11 2.3 Goals for Designers of Parallel Algorithms : : : : : : : : : : : : : : : : : 15 2.4 Some final Comments : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16 2.4.1 The defualt assumption regarding shared assumption access resolution : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16 2.4.2 NC : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16 2.4.3 On selection of material for these notes : : : : : : : : : : : : : : : 17 2.4.4 Level of material : : : : : :