文档介绍：Vector Models for Data-puting
Guy E. Blelloch
The MIT Press
Cambridge, Massachusetts
London, England
c 1990 Massachusetts Institute of Technology
vi
Contents
Preface xiii
Acknowledgments xv
1 Introduction 1
Parallel Vector Models . . . ........................ 3
Vector Instructions ............................. 5
Implementation . . ............................. 9
........................... 10
I Models 15
2 Parallel Vector Models 19
The Vector Random Access Machine . ................... 19
to P-RAM Models ....................... 22
to Circuit work Models . ............... 27
-VectorModels..................... 30
Selecting Primitives ............................. 31
Other Issues ................................. 31
Serially Optimal Algorithms . ................... 31
plexity......................... 32
Equal Time Assumption . . . ................... 32
Do We Need the Scalar Memory? . . ............... 32
Conclusion ................................. 33
3 The Scan Primitives 35
Why Scan Primitives? ............................ 37
vii
viii CONTENTS
................................... 39
Example: Line-of-Sight . . . ........................ 40
Simple Operations ............................. 42
Example: Split Radix Sort . . ................... 43
Segments and Segmented Scans . . . ................... 45
Example: Quicksort ........................ 46
Notes on Segments . ........................ 47
Allocating Elements ............................. 48
Example: Line Drawing . . . ................... 50
Notes on Allocating ........................ 51
Long Vectors and Load Balancing . . ................... 51
LoadBalancing........................... 53
Example: Halving Merge . . . ................... 54
Notes on