Associative Computing: A Programming Paradigm for Massively Parallel Computers

by Jerry L. Potter

Overview

Integrating associative processing concepts with massively parallel SIMD technology, this volume explores a model for accessing data by content rather than abstract address mapping.

Product Details

ISBN-13:	9780306439872
Publisher:	Springer-Verlag New York, LLC
Publication date:	09/28/1991
Series:	Frontiers in Computer Science Series
Pages:	304
Product dimensions:	6.69(w) x 9.45(h) x (d)

Table of Contents

1. Introduction.- 1.1. SITDAC Terminology.- 1.2. The SITDAC Model.- 1.3. SITDAC versus Other Models.- 1.4. Hardware Ramifications of SITDAC.- 1.5. SITDAC Algorithms.- 1.6. History.- 1.7. The Nature of SITDAC Programming.- 1.8. Reduced Programming Complexity.- 1.9. Throughput Analysis.- 1.10. Conclusion.- 2. Basic Concepts of Associative Programming.- 2.1. SIMD Parallelism.- 2.2. Flow of Control.- 2.3. The Classroom Model.- 2.4. Memory Allocation.- 2.5. Massive Parallel Searching.- 2.6. Tabular Arrays.- 2.7. Bit-Serial Arithmetic.- 2.8. Responders and Numeric Searching.- 2.9. Responder Iteration.- 2.10. Corner Turning.- 2.11. Bucket-Brigade Communication.- 2.12. Data Mapping.- 2.13. Data Replication.- 2.14. Conclusion.- 3. An Associative Model of Computation.- 3.1. The SITDAC Model of Computation.- 3.2. Cycle Nesting.- 3.3. Items and Expressions.- 3.4. Item Declarations.- 3.5. The Associative Statement.- 3.6. The Allocate and Release Statements.- 3.7. The If Statement.- 3.8. The For and While Statements.- 3.9. The Loop Statement.- 3.10. The Get Statement.- 3.11. The Next Statement.- 3.12. The Any Statement.- 3.13. The Setscope Statement.- 3.14. Maximum, Minimum, Nth and Count.- 3.15. Item Equivalences.- 3.16. ASC Pronouns and Articles.- 3.17. Module Types—Main and Subroutine.- 3.18. The I/O Statements.- 3.19. Interprocessor Communication.- 3.20. Contiguous Data Allocation.- 3.21. Indirect Addressing.- 3.22. Conclusion.- 4. Elementary ASC Programs.- 4.1. Simple Arithmetic Tasks.- 4.2. Associative Stacks and Queues.- 4.3. A Dataflow Interpreter.- 4.4. Minimal Spanning Tree.- 4.5. Conclusion.- 5. Associative Data Structures.- 5.1. An Associative Program.- 5.2. Structure Codes.- 5.3. Data Structures as Extended Associations.- 5.4. Simultaneous Multiple Data Organizations.-5.5. Generalized Array Data Structure Codes.- 5.6. Associative Data Structure References.- 5.7. Data Structure Code Manipulation.- 5.8. Synonymous Data Structures.- 5.9. Lists and Linked Lists.- 5.10. Structure-Code Functions.- 5.11. List Manipulation.- 5.12. Structure-Code Searching Functions.- 5.13. Structure-Code I/O (SCIO).- 5.14. Structure Codes for Graphs.- 5.15. Conclusion.- 6. ASC Recursion.- 6.1. The Recursewhile Construct.- 6.2. A Simple Recursewhile Example.- 6.3. How to Use Recursewhile.- 6.4. A Complex Recursewhile Example.- 6.5. Conclusion.- 7. Complex Searching.- 7.1. A Brief OPS5 Background.- 7.2. Pattern Data Structures.- 7.3. Local and Global Variables.- 7.4. The Andif Statement.- 7.5. The Andfor Statement.- 7.6. Flow of Control for And Constructs.- 7.7. Conclusion.- 8. Context-Sensitive Compilation.- 8.1. Context Sensitivity.- 8.2. A Brief Overview.- 8.3. Context-Sensitive Compilation.- 8.4. Execution of a Procedural Rule.- 8.5. Conclusion.- 9. Associative Prolog.- 9.1. Background.- 9.2. Unification.- 9.3. The Binding Association.- 9.4. Search Organization.- 9.5. Inference Engine.- 9.6. Clause Filtering.- 9.7. Binding Variables.- 9.8. Prolog I/O.- 9.9. Example of a Prolog Program.- 9.10. Additional Details.- 9.11. Conclusion.- 10. An Associative Processor Design.- 10.1. Design Rationale.- 10.2. Re-locatable Data.- 10.3. Communication Paths.- 10.4. The Basic Design.- 10.5. VLSI Organization.- 10.6. Associative Multitasking/Multiuser Parallelism.- 10.7. The Basic Associative Intermediate Level Instruction Set.- 10.8. Conclusion.- Appendix. ASC Tables.- References.