THE CARTESIAN PRODUCT PROBLEM AND IMPLEMENTING PRODUCTION SYSTEMS ON RECONFIGURABLE MESHES

Let A and B be two groups of up to n elements distributed on the first row of an n × n reconfigurable mesh, and C_A,B a subset of the cartesian product A × B satisfying some unknown condition C. Only one broadcasting step is needed in order to compute C_A,B's elements. However, the problem of moving C_A,B's elements to the first row in optimal time (so that they can be further processed) is not trivial. The conditional cartesian product (CCP) problem is to move C_A,B's elements to the first row in steps. This requires optimizing the cartesian product operation such that C_A,B's elements will be optimally scattered in the mesh, so that O(n) elements can be retrieved in a single step as opposed to elements needed if the cartesian product is not optimized). We give a deterministic algorithm that for any A, B, C solves this problem in steps, and an "adaptive" randomized algorithm whose optimality is verified by experimental results. Note that the CCP is a case where we overcome the inherent limitation of the reconfigurable mesh, namely, the inability to perform fast routing of packets located in a small area.

We also present the model of production systems, in which computation is realized by executing cartesian productions of subsets in a common element space. Production systems are useful for database applications, expert systems, and can even be used as a general parallel programming language. Solving the CCP problem allows us to devise an efficient implementation for production systems on the reconfigurable mesh. In this way the reconfigurable mesh is shown to be an attractive architecture for database machines and for parallel programming as well.