Compiling for Computational Origami Using Probabilistic Optimization

Robert Scott French

May 21, 1990

Submitted to the Department of Electrical Engineering and Computer Science in Partial Fulfillment of the Requirements for the Degree of Bachelor of Science in Computer Science and Engineering at the Massachusetts Institute of Technology.

© 1990 Robert Scott French

The author hereby grants to MIT permission to reproduce and to distribute copies of this thesis document in whole or in part.

ABSTRACT
The term computational origami refers to a class of computational architectures that consist of systolic arrays of processors arranged in a tesselable, mosaic architecture. This interconnection strategy provides a computational origami architecture with certain properties, including the ability to ``fold'' the architecture to almost arbitrarily select space-time tradeoffs. This thesis presents a compiler that can be used to compile simple, non-recursive programs into a two-dimensional origami architecture called the alternate-slant network. Probabilistic optimizations based on simulated annealing are proposed which result in a 50%savings on array size.

Acknowledgments

Many people have helped me with my academic career, and I would like to take this opportunity to thank them. I would first like to thank my parents, whose support of my computer interests throughout my life has enabled me to get to where I am today. I would also like to thank Isaac Chuang for introducing me to computational origami and for participating in many hours of discussion about how to compile for an origami computer, the members of the Student Information Processing Board, who provided me with a social atmosphere in which I could flame about random ideas, and my thesis advisor, Tom Knight, who gave me free reign on my thesis topic. Finally, special thanks go to Carol Smith for proofreading drafts of this thesis.

• Contents
• List of Figures
• List of Tables
• Introduction
• Overview of Origami
  • Introduction
  • A Sample Array
  • Folding
    • Depthwise Folding
    • Widthwise Folding
    • The Foldability Criteria
    • The Use of Delay Lines
    • Boundary Conditions
  • Higher-Dimensional Origami
  • Why Use Computational Origami?
• Compiling for Computational Origami
  • Introduction
  • The Architecture
  • The Routing Algorithm
    • Preliminaries
    • Module Placement
    • Routing
  • An Example
• Optimization
  • Simulated Annealing
    • Mutations
      • Local Module Swapping
      • Module Movement
      • Input/Output Permutation of Modules
    • The Cost Function
  • Empirical Results
• Future Work
• Conclusion
• References
• The Compiler
• The Input Language
• Running the Compiler
• The Architecture Specification
• The Library Specification
• Example
• Error Messages