Tiered Algorithm for Distributed Process Quiescence and Termination Detection

The Tiered Algorithm is presented for time-efficient and message-efficient detection of process termination. It employs a global invariant of equality between process production and consumption at each level of process nesting to detect termination, regardless of execution interleaving order and network transit time. Correctness is validated for arbitrary process launching hierarchies, including launch-in-transit hazards, where processes are created dynamically based on runtime conditions for remote execution. The performance of the Tiered Algorithm is compared to three existing schemes with comparable capabilities, namely, the Chandrasekaran and Venkatesan (CV), Lai, Tseng, and Dong (LTD), and Credit termination detection algorithms. For synchronization of X tasks terminating in E epochs of idle processing, the tiered algorithm is shown to incur O(E) message count complexity and O(T lg T) message bit complexity while incurring detection latency corresponding to only integer addition and comparison. The synchronization performance in terms of message overhead, detection operations, and storage requirements are evaluated and compared across numerous task creation and termination hierarchies.     

A partitioning algorithm for technoiogy-mapped designs onsingle-chip emulation systems

Reconfigurable single-chip emulation systems were proposed as an alternative to multichip emulation systems. Because they cannot be emulated on a single chip at once, large designs are sliced into partitions that are downloaded and executed sequentially on the same reconfigurable emulation chip. In this paper, we address the problem of partitioning a design on a reconfigurable single-chip emulator under resource constraints. First, we extract an acyclic flow graph of the design to be emulated. Then, we model the problem as an integer linear programming problem (IP) based on the acyclic flow graph of the design where the structure of the assignment and precedence constraints produce a tight formulation. To partition a design, our algorithm uses two distinct steps with different objectives. In the first step, we minimize the number of cycles needed to schedule every look-up table (LUT) in the circuit. Then flip-flops (FFs) are inserted into the appropriate cycles of the schedule in the second step. Experiments are conducted on small- and medium-size circuits from the MCNC Partitioning93 benchmark suite. The obtained results show that our algorithm produces optimal partitioning schedules     

A tree-matching chip

Tree matching is an important problem used for three-dimensional object recognition in image understanding and vision systems. The objective of tree matching is to find the set of nodes at which a pattern tree matches a subject tree. In this paper, we describe the design and implementation of a very large scale integration (VLSI) chip for tree pattern matching. The architecture is based on an iterative algorithm that is mapped to a systolic array computational model and takes O(t(n+a)) time to profess a subject of size n using a processors where a is the length of the largest substring in the pattern and t is the number of substrings in the pattern. The variables and nonvariables of the pattern tree are processed separately, which simplifies the hardware in each processing element. The proposed partitioning strategy is independent of the problem size and allows larger strings to be processed based on the array size. A prototype CMOS VLSI chip has been designed using the Cadence design tools and the simulation results indicate that it will operate at 33.3 MHz     

Routing on field-programmable switch matrices

In this paper, we address the problem of routing nets on field programmable gate arrays (FPGAs) interconnected by a switch matrix. We extend the switch matrix architecture proposed by Zhu et al. (1993) to route nets between FPGA chips in a multi-FPGA system. Given a limited number of routing resources in the form of programmable connection points within a two-dimensional switch matrix, this problem examines the issue of how to route a given net traffic through the switch matrix structure. First, we define the problem as a general undirected graph in which each vertex has one single color among six possible colors and formulate it as a constraint satisfaction problem. This is further modeled as a 0-1 multidimensional knapsack problem for which a fast approximate solution is applied. Experimental results show that the accuracy of our proposed heuristic is quite high for moderately large switch matrices.     

Multiterminal net routing for partial crossbar-based multi-FPGA systems

Multi-FPGA (field-programmable gate arrays) systems are used as custom computing machines to solve compute-intensive problems and also in the verification and prototyping of large circuits. In this paper, we address the problem of routing multiterminal nets in a multi-FPGA system that uses partial crossbars as interconnect structures. First, we model the multiterminal routing problem as a partitioned bin-packing problem and formulate it as an integer linear programming problem where the number of variables is exponential. A fast heuristic is applied to compute an upper bound on the routing solution. Then, a column generation technique is used to solve the linear relaxation of the initial master problem in order to obtain a lower bound on the routing solution. This is followed by an iterative branch-and-price procedure that attempts to find a routing solution somewhere between the two established bounds. In this regard, the proposed algorithm guarantees an exact-routing solution by searching a branch-and-price tree. Due to the tightness of the bounds, the branch-and-price tree is small resulting in shorter execution times. Experimental results are provided for different netlists and board configurations in order to demonstrate the algorithms performance. The obtained results show that the algorithm finds an exact routing solution in a very short time.