| Specialized parallel machines have been designed and built for specific tasks. Traditionally, pyramid machines have been used for image processing problems. We examine here techniques for extending the use of pyramid networks.;By mapping a common data structure and computation graph, the binary tree, onto the pyramid structure, we show that pyramid machines may handle also recursive tasks. We give algorithms for placing the complete binary tree, the X-tree, and, by composition, arbitrary binary trees onto pyramids. We construct these mappings to minimize costs such as communication delay between adjacent processors and contention for message links.;We look at the issue of mapping a structure which contains a large number of processes to a machine which contains a smaller number of processors. We compress pyramids into arbitrarily small pyramids. Then, by detailed placement and composition, we show how to map X-trees, complete binary trees and arbitrary binary trees onto smaller pyramids.;One class of these problems, known as the Single Row Routing problem, involves routing wires on one or more layers when the pins are laid out along a straight line. To prevent electrical interference, the wires are laid out in tracks parallel to the row of pins and distinct wires are prohibited from crossing.;Formally, the Single Row Routing problem involves determining the feasibility of any wiring in the minimum number of tracks. We dramatically cut the search space of an exhaustive search so that larger instances of the problem may be solved in a reasonable amount of time. We show that allowing an arbitrary number of extra parallel tracks does not decrease the complexity of determining the routing.;When we are allow to route wires on more than one layer the problem of determining the feasibility of a wiring in a minimum number of layers but with an arbitrary number of parallel tracks is also known to be NP-complete. A long-standing open problem has been the complexity of the Single Row Routing problem on multilayers when the number of parallel tracks per layer is fixed. We show that this version of the problem is also NP-complete. (Abstract shortened with permission of author.)... |
