Parallel Processing for Artificial Intelligence 1 (eBook)

Front Cover 1
Parallel Processing for Artificial Intelligence 1 4
Copyright Page 5
Table of Contents 10
PREFACE 6
EDITORS 12
AUTHORS 14
PART I: IMAGE PROCESSING 18
Chapter 1. A Perspective on Parallel Processing in Computer Vision and Image Understanding 20
1. Introduction 20
2. Parallelism in Vision Systems 22
3. Representation Based Classification of Vision Computations 23
4. Issues in Data and Computation Partitioning 25
5. Architectural Requirements 29
6. Future Directions 34
Acknowledgments 36
References 36
Chapter 2. On Supporting Rule-Based Image Interpretation Using a Distributed Memory Multicomputer 38
1. Introduction 38
2. Software and Hardware Strategies for Supporting RBS 40
3. AIMS: A Multi-Sensor Image Interpretation System 43
4. Parallel Implementation 47
5. Discussion 52
6. Conclusion 54
References 55
Chapter 3. Parallel Affine Image Warping 62
1. Introduction 62
2. Forward versus inverse algorithms in affine image warping 64
3. Other important characteristics of affine image warping 66
4. Machines 66
5. Classification of implementations 67
6. Systolic methods 69
7. Data partitioned methods 74
8. A scanline method 77
9. A Sweep-Based Method 78
10. Conclusions 82
References 83
Chapter 4. Image Processing On Reconfigurable Meshes With Buses 84
Abstract 84
1. Introduction 84
2· Data Manipulation Operations 88
3. Area And Perimeter Of Connected Components 91
4. Shrinking And Expanding 94
5. Clustering 97
6. Template Matching 99
7. Conclusions 104
8. References 104
PART II: SEMANTIC NETWORKS 110
Chapter 5. Inheritance Operations in Massively Parallel Knowledge Representation 112
1. Massively Parallel Knowledge Representation 112
2. Schubert's Tree Encoding of IS-Á Hierarchies 113
3. How to Achieve the Same Effect Without Trees 115
4. Parallelizing the Update Algorithm 119
5. Inheritance Terminology 120
6. Upward-Inductive Inheritance 121
7. Downward Inheritance Algorithm 122
8. Upward-Inductive Inheritance Algorith 124
9. Experimental Results 125
10. Conclusions 128
Acknowledgement 128
References 129
Chapter 6. Providing Computationally Effective Knowledge Representation via Massive Parallelism 132
1. Introduction 132
2. Description of PARKA 134
3. Performance 139
4. Future & Related Work
5. Conclusion 149
6. Acknowledgments 150
References 150
PART III: PRODUCTION SYSTEMS III 154
Chapter 7. Speeding Up Production Systems: From Concurrent Matching to Parallel Rule Firing 156
1. Introduction 156
2. A Generic Production System Architecture 158
3. State-Saving Algorithms 160
4. Parallel Execution of Rete 164
5. Compile Time Optimization of Rete 168
6. Parallel Rule Firing 168
7. Discussion 173
References 174
Chapter 8. Guaranteeing Serializability in Parallel Production Systems 178
1. Execution Models for Production Systems 179
2. The Serialization Problem 184
3. Ishida and Stolfo's Work 186
4. Definitions and Tests 188
5. Solution to the Serialization Problem 194
6. Algorithms to Guarantee Serializaibilty 199
7. Performance Analysis 205
8. Related Work 215
9. Conclusions 218
10. Acknowledgments 219
References 219
PART IV: MECHANIZATION OF LOGIC IV 224
Chapter 9. Parallel Automated Theorem Proving 226
Abstract 226
1. Introduction 226
2. Classification of Parallelization Approaches 228
3. Partitioning-based Parallel Theorem Provers 233
4. Competition-based Parallel Theorem Provers 255
5. Summary 264
Appendix 267
References 268
Chapter 10. Massive Parallelism in Inference Systems 276
1. Parallelism in Logic 276
2. Massive Parallelism 279
3. The Potential of Massive Parallelism for Logic 282
4. CHCL: A Connectionist Inference System 285
References 288
Chapter 11. Representing Propositional Logic and Searching for Satisfiability in Connectionist Networks 296
1. Introduction 296
2. The energy paradigm 298
3. Propositional Logic and Energy Functions 302
4. Experimental Results 307
5. Discussion 311
Acknowledgment 315
References 316
PART V: CONSTRAINT SATISFACTION 320
Chapter 12. Parallel and Distributed Finite Constraint Satisfaction: Complexity, Algorithms and Experiments 322
1. Introduction 322
2. Properties of Constraint Networks 325
3. A Parallel Algorithm and Complexity 332
4. A Distributed Algorithm and Complexity 338
5. A Coarse-Grain Distributed Algorithm 341
6. Experimental Results 346
7. Conclusions 349
Acknowledgements 349
References 349
Chapter 13. PARALLEL ALGORITHMS AND ARCHITECTURES FOR CONSISTENT LABELING 352
1. Introduction 352
2. Consistent Labeling 353
3. Previous Designs 355
4. Implementations on Special Purpose Architectures 357
5. Implementations on General Purpose Parallel Architectures 372
6. Conclusion 377
Acknowledgement 377
References 377
PART VI: OTHER TOPICS 380
Chapter 14. Massively Parallel Parsing Algorithms for Natural Language 382
1. Introduction 382
2. Tree Adjoining Grammar 387
3. The Connection Machine Model CM-2 396
4. Parsing Sparse TAGs: Parallel Algorith I 399
5. Parsing Sparse TAGs: Parallel Algorithm II 404
6. Parallel Algorithms for Parsing Dense TAGs 409
7. Conclusions and Future Work 417
8. Appendix 419
References 422
Chapter 15. Process Trellis and FGP: Software Architectures for Data Filtering and Mining 426
1. Introduction 426
2. Linda and the Master/Worker model 427
3. The FGP Machine 429
4. The Process Trellis 434
5. Combining the Trellis and FGP programs for Real-Time Data Management 439
6. An Integrated Program for Network Monitoring 441
7. Conclusions 443
References 443