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.
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.
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.