Recently, due to the development of design and manufacturing technologies for VLSI systems, an embedded system becomes more and more complex. Consequently, not only the performance of chips, but also the flexibility and dynamic adaptation of the implemented systems are required. To achieve these requirements, a partially reconfigurable device is promising. In this paper, we propose an efficient data structure to manage the reconfigurable units. And then, on the assumption that each task utilizes the rectangle shaped resources, a very simple MER enumeration algorithm based on this data structure is proposed. By utilizing the result of MER enumeration, the free space on the reconfigurable device can be used sufficiently. We analyze the complexity of the proposed algorithm and confirm its efficiency by experiments.

In deep-submicron technologies, process variations can significantly affect the performance and yield of VLSI chips. As a countermeasure to the variations, post-silicon tuning has been proposed. Deskew, where the clock timing of flip-flops (FFs) is tuned by inserted programmable delay elements (PDEs) into the clock tree, is classified into this method. We propose a novel deskew method that decides the delay values of the elements by measuring a small amount of FFs' clock timing and presuming the rest of FFs' clock timings based on a statistical model. In addition, our proposed method can determine the discrete PDE delay value because the rewriting constraint satisfies the condition of total unimodularity.

In this paper, we propose a novel migration method. In this method, the resultant placement retains the structure of the original placement, called model placement, as much as possible. For this purpose, we minimize the sum of the difference in area between the model placement and the relocated one and the total amount of displacement between them. Moreover, to achieve a short runtime, we limit the solution space and change the packing origin in the optimization process. We construct the system on Sequence-Pair. Experimental results show that our approach preserves the chip area and the overall circuit structure with 98% less runtime than that realized by naive simulated annealing.

The most basic cross-talk minimization problem is to assign given n intervals to n parallel tracks where the cross-talk is defined between two intervals assigned to the adjacent tracks with the amount linear to parallel running length. This paper solves the problem for the case when any pair of intervals intersects and the objective is to minimize the sum of cross-talks. We begin the discussion with the fact that twice the sum of lengths of n/2 shortest intervals is a lower bound. Then an interval set that attains this lower bound is characterized with a simple assignment algorithm. Some additional considerations provide the minimum cross-talk for the other interval sets. The main procedure is to sort the intervals twice with respect to the length of left and right halves of intervals.

In this paper, we propose a fast Maximal Empty Rectangle (MER) enumeration algorithm for online task placement on reconfigurable Field-Programmable Gate Arrays (FPGAs). On the assumption that each task utilizes rectangle-shaped resources, the proposed algorithm can manage the free space on FPGAs by an MER list. When assigning or removing a task, a series of MERs are selected and cut into segments according to the task and its assignment location. By processing these segments, the MER list can be updated quickly with low memory consumption. Under the proof of the upper limit of the number of the MERs on the FPGA, we analyze both the time and space complexity of the proposed algorithm. The efficiency of the proposed algorithm is verified by experiments.

This paper presents a novel algorithm for crosspoint assignment (CPA) that takes into consideration crosstalk noise and shielding effects in deep sub-micron design. We introduce a conditional constraint which is imposed on a sensitive net-pair to detach one net from the other or to put another insensitive net between them for shielding. We provide two algorithms which can handle the conditional constraint: One is based on an ILP, which outputs an exact optimum solution. The other is a fast heuristics whose time complexity is O(n2 log n), where n is the number of pins. In experiments, we tested these algorithms for industrial examples. The results showed that the conditional constraint for shielding released algorithms from a tight space of feasible assignments. Our heuristics ran quickly and attained near optimum solutions.

In the recent LSI design, it is difficult to obtain a placement which satisfies both design constraints and specifications due to the increase of the circuit size, the progress of the manufacturing technology, and the speed-up of the circuit performance. Analytical placement methods are promising to obtain the placement which satisfies both design constraints and specifications. Although existing analytical placement methods obtain the placement with the short wire length, the obtained placement has overlap. In this paper, we propose Overlap Removable Area as an overlap evaluation method for an analytical placement method. Experiments show that the proposed evaluation method is effective for removing overlap in the analytical placement method.

The switch-block architecture of FPGAs is discussed to see a good balance between programmable-switch resources and routability. For the purpose, FPGAs are assumed to have certain extremal structures, whose switch-blocks consist of parallel or complete switch-sets where a switch-set is a set of switches between two sides of the switch-block. A polynomial time detailed-routing algorithm for a given global-routing is presented if the switch-block consists of two or less parallel switch-sets or three that form a cycle. For other FPGAs, the corresponding decision problem is proved to be -complete. A best compromise between switch resources and routability is offered.

Multi-FPGA systems, which consist of multiple FPGAs and a printed circuit board connecting them, are useful and important tools for prototyping large scale circuits, including SoCs. In this paper, we propose a method for optimizing inter-FPGA signal transmission to accelerate the system frequency of multi-FPGA prototyping systems and shorten prototyping time. Compared with the number of I/O pins of an FPGA, the number of I/O signals between FPGAs usually becomes very large. Thus, time-multiplexed I/Os are used to resolve the problem. On the other hand, they introduce large delays to inter-FPGA I/O signals, and much lower the system frequency. To reduce the degradation of the system frequency, we have proposed a method for optimally selecting signals to be time-multiplexed and signals not to be time-multiplexed. However, this method assumes that there exist physical connections (i.e., wires on the printed circuit board) between every pair of FPGAs, and cannot handle I/O signals between a pair of FPGAs that have no physical connections between them. Thus, in this paper, we propose a method for obtaining indirect inter-FPGA routes for such I/O signals, and then combine the indirect routing method and the time-multiplexed signal selection method to realize effective time-multiplexing of inter-FPGA I/O signals on systems with various topologies.

A challenge to an automated layout of analog ICs starts with the insight into high quality placements crafted by experts. We observe first that matched devices or elemental functions such as input, output, amplifiers, etc are clustered. Second, devices in the same cluster are located faithfully to the drawn schema. Third, these two features are simultaneously fulfilled in a well-compacted placement. This paper proposes a novel device-level placement that simulates the above features based on Sequence-Pair. A slight modification of the meaning, say, of relation "A is left-of B" to relation "A is not right-of B" enlarges the freedom and allows a neater compaction of clusters allowing zigzag border curves. As the consequence, clusters are placed faithfully to relative position in the schema. We tested our algorithm for industrial instances and compared results with those by manual design. The results showed better features in performance figures than the those of manual designs by, on average, 13.5% and 21.2% with respect to the area and total net-length.

The success in topdown design of recent huge system LSIs is in a seamless transfer of the information resulted from the high level design to the lower level of floorplanning. For the purpose, we introduce a new concept abstract floorplan which is included in the output of high level design. From the abstract floorplan, the pillar blocks are derived which are critical sets of blocks that are expected to determine the width and height of the chip, named the frame. Since the frame and pillar blocks are obtained in the high level stage, they are useful to keep the consistency in the low level physical design if we apply optimization regarding them as constraints. Experiments to MCNC benchmarks showed that abstract floorplanning by pillar blocks output a placement faithful to the one physically optimized block placement with respect to the chip area and the wire-length.

Lately, time-multiplexed I/Os for multi-device implementations (e.g., multi-FPGA systems), have come into practical use. They realize multiple I/O signal transmissions between two devices in one system clock cycle using one I/O wire between the devices and multiple I/O clock cycles. Though they ease the limitation of the number of I/O-pins of each device, the system clock period becomes much longer approximately in proprotion to the maximum number of multiplexed I/Os on a signal path. There is no conventional partitioning algorithm considering the effect of time-multiplexed I/Os directly. We introduce a new cost function for evaluating the suitability of a bipartition for multi-device implementations with time-multiplexed I/Os. We propose a performance-driven bipartitioning method VIOP which minimizes the value of the cost function. Our method VIOP combines three algorithms, such that i) min-cut partitioning, ii) coarse performance-driven partitioning, iii) fine performance-driven partitioning. For min-cut partitioning and coarse performance-driven partitioning, we employ a well-known conventional bipartitioning algorithms CLIP-FM and DUBA, respectively. For fine performance-driven partitioning for the final improvement of a partition, we propose a partitioning algorithm CAVP. By our method VIOP, the average cost was improved by 10.4% compared with the well-known algorithms.

The shape-based routing needs a routing architecture with a geometrical computation framework on it. This paper introduces a novel routing architecture, Oct-Touched Tile (OTT), with a geometrical computation method along the horizontal- and vertical-constraints. The architecture is represented by the tiles spreading over the 2-D plane. Each tile is flexible to satisfy the constraints imposed for non-overlapping and sizing request. In this framework, path finding and shape-based sizing are executed on the same architecture. In experiments, our system demonstrates the performance comparable to a commercial tool. In addition, we show potential of OTT by introducing several ideas of extensions to analog layout constraints.

In multi-FPGA prototyping systems for circuit verification, serialized time-multiplexed I/O technique is used because of the limited number of I/O pins of an FPGA. The verification time depends on a selection of inter-FPGA signals to be time-multiplexed. In this paper, we propose a method that minimizes the verification time of multi-FPGA systems by finding an optimal selection of inter-FPGA signals to be time-multiplexed. In the experiments, it is shown that the estimated verification time is improved 38.2% on average compared with conventional methods.