Parallel algorithms for the reconfigurable mesh

The reconfigurable mesh is an architecture for a parallel model of computing in which processors are arranged in a grid. This model allows processors to create buses of various configurations; each processor, upon analyzing local information decides which bus it will belong to. Once constructed, the bus is capable of transmitting data very quickly. All processors operate the same set of instructions in SIMD fashion and may read from the bus simultaneously. Only one processor may broadcast data onto the bus at a time.; Presented in this work are four parallel algorithms for the reconfigurable mesh. The first two algorithms perform the Hough transform. The Hough transform is a line, curve, and shape detection technique used in computer graphics. The first algorithm is a constant time technique which computes the Hough transform of N points and p angles using a mesh of {dollar}Np times p {lcub}rm log{rcub}sp2 N{dollar} processors. The second algorithm is a constant time approach which performs the same task using {dollar}O(pNsp{lcub}3over2{rcub}){dollar} processors.; The third algorithm performs sorting of n items using a 3-D mesh of dimensions {dollar}sqrt{lcub}n{rcub} times sqrt{lcub}n{rcub} times sqrt{lcub}n{rcub}{dollar}. It uses a radix sort and operates in constant time.; The last algorithm solves the channel assignment problem. This problem in circuit lay-out considers a two-sided printed circuit board which contains vertical lines on one side and horizontal lines, or channels, on the other. The objective is to place n pairs of components on the board so that no channel may have a portion which contains overlapping or conflicting pairs. The least number of channels are assigned. Given is a constant time algorithm which uses a {dollar}sqrt{lcub}2n{rcub} times sqrt{lcub}2n{rcub} times 17 sqrt{lcub}2n{rcub}{dollar} reconfigurable mesh to assign channels to n intervals. To accomplish this, a technique is presented which creates a linked list of n items in constant time.; Preceding the description of the four algorithms is a discussion of basic algorithmic tools used in parallel algorithms for this architecture as well as a review of actual hardware that has implemented this model.