Narrow Results

Partially reconfigurable field-programmable gate arrays (FPGAs) allow parts of the chip to be configured at runtime where each part could hold an independent task. Online placement of these tasks result in area fragmentation leading to poor utilization of chip resources.

In this paper, we propose a new metric for measuring area fragmentation. The new fragmentation metric gives an indication to the continuity of the occupied (or free) space and not the amount of occupied space. We show how this metric can be extended for multidimensional structures. We also show how this metric can be computed efficiently at runtime. Next, we use this measure during online placement of tasks on FPGAs, such that the chip fragmentation is reduced. Our results show improvement of chip utilization when using this fragmentation aware placement method over other placement methods with well-known bottom left, first fit, and best-fit placement strategies. In real-time environment, we achieve an improvement in miss ratio when using the fragmentation-aware placement over the bottom left placement strategy.

In partially reconfigurable devices like FPGA, logic resources and communication channels can be reconfigured without affecting other section of the device. This allows parallel execution of multiple tasks on a FPGA. Due to limited resources on a FPGA, an effective management for efficient execution of tasks is required.

We present a new approach for management of FPGA logic resources and also communication channels in an online task placement. The approach creates communication channels between the tasks and also tasks with I/O elements without requiring extra computation overhead. We present a fast algorithm for searching MERs for management of FPGA space. Then, we present a exact routing algorithm to find distance and create exact path between two set of tasks. A new fitting strategy based on the rate of communication between the tasks is also presented. The results indicate the proposed strategy and also its combination with some other known strategies can improve the quality of placement.

Dynamic Partially Reconfiguration (DPR) designs provide additional benefits compared to traditional FPGA application. However, due to the lack of support from automatic design tools in current design flow, designers have to manually define the dimensions and positions of Partially Reconfigurable Regions (PR Regions). The following fine-grained placement for system modules is also limited because it takes the floorplanning result as a rigid region constraint. Therefore, the manual floorplanning is laborious and may lead to inferior fine-grained placement results. In this paper, we propose to integrate PR Region floorplanning with fine-grained placement to achieve the global optimization of the whole DPR system. Effective strategies for tuning PR Region floorplanning and apposite analytical evaluation models are customized for DPR designs to handle the co-optimization for both PR Regions and static region. Not only practical reconfiguration cost and specific reconfiguration constraints for DPR system are considered, but also the congestion estimation can be relaxed by our approach. Especially, we established a two-stage stochastic optimization framework which handles different objectives in different optimization stages so that automated floorplanning and global optimization can be achieved in reasonable time. Experimental results demonstrate that due to the flexibility benefit from the unification of PR Region floorplanning and fine-grained placement, our approach can improve 20.9% on critical path delay, 24% on reconfiguration delay, 12% on congestion, and 8.7% on wire length compared to current DPR design method.

Satisfiability modulo theories (SMT) is an area concerned with checking the satisfiability of logical formulas over one or more theories. SMT can be well tuned to solve several of the most intriguing problems in electronic design automation (EDA). Analog placers use physical constraints to automatically generate small sections of layout. The work presented in this paper shows that SMT solvers can be used for the automation of analog placement, given some physical constraints. We propose a tool that uses Microsoft Z3 SMT solver to find valid placement solutions for the given analog blocks. Accordingly, it generates multiple layouts that fulfill some given constraints and provides a variety of alternative layouts. The user has the option to choose one of the feasible solutions. The proposed system uses the quantifier-free linear real arithmetic (QFLRA), which makes the problem decidable. The proposed system is able to generate valid placement solutions for benchmarks. For benchmarks that have many constraints and few geometries, the proposed system achieves a speedup that is 10 times faster than other recently used approaches.

DNA computation is an emerging technology to perform complex information processing at the nanoscale era. Molecular programming with localized DNA hybridization is a systematic, parallel and scalable approach for DNA computation. Considerable methods are developed for the design of Localized DNA circuits. Due to significant theoretical and technological difference between this technology and conventional electronic system, a customized design flow for this technology is a real requirement. We proposed a customized DNA cell placement algorithm for localized DNA hybridization technology in this paper. The main objectives in the proposed placement algorithm are minimizing the die footprint and total signal propagation path. Our implementations and simulations show the feasibility and efficiency of the proposed placement algorithm.

By scaling the semiconductor industry to nano-scale era, design and prototyping cost of cell-based Application-Specific Integrated Circuits (ASICs) becomes more expensive and it makes Field Programmable Gate Arrays (FPGAs) more popular among designers. However, there is a gap between FPGAs and ASICs in terms of timing, dynamic power consumption and logic density. Three-dimensional integration, particularly in the full monolithic process, has been considered as a promising solution to reduce the performance gap of ASICs and FPGAs. In this paper, two new architectures for the monolithically integrated 3D-FPGAs are introduced. In order to exploit the great potentials of the suggested architectures, a new three-dimensional FPGA placement algorithm is proposed thereafter. The proposed placement algorithm, named JABE, is the first of its kind that enables designers to take advantages of the large number of vertical interconnections in the monolithically stacked 3D-FPGAs. Our experiments show a 24% timing improvement for the new architectures and CAD algorithms compared with the conventional TSV-based 3D-FPGAs and design flows. In addition, improvements in terms of the total wirelength and area footprint are reported for the proposed placement algorithms and new architectures.

Microfluidic biochips are extensively utilized in biochemistry procedures due to their low cost, high precision and efficiency when compared to traditional laboratory procedures. Recent, computer-aided design (CAD) techniques enable a high performance in digital microfluidic biochip design. A key part in digital microfluidic biochip CAD design is the biochip placement procedure which determines the physical location for biological reactions during the physical design. For the biochip physical design, multiple objects need to be considered, such as the size of the chip and the total operation time. In this paper, a multi-objective optimization is proposed based on Markov decision processes (MDPs). The proposed method is evaluated on a set of standard biochip benchmarks. Compared to existing works, experimental results show that the total operation time, the capacity for routing and the chip size can be optimized simultaneously.

We consider the problem of computing large connected regions in a triangulated terrain of size n for which the normals of the triangles deviate by at most some small fixed angle. In previous work an exact near-quadratic algorithm was presented, but only a heuristic implementation with no guarantee was practicable. We present a new approximation algorithm for the problem which runs in O(n/∊²) time and—apart from giving a guarantee on the quality of the produced solution—has been implemented and shows good performance on real data sets representing fracture surfaces consisting of around half a million triangles. Further we present a simple approximation algorithm for a related problem: given a set of n points in the plane, determine the placement of the unit disk which contains most points. This algorithm runs in linear time as well.

In geo-distributed cloud systems, a key challenge faced by cloud providers is to optimally tune and configure the underlying cloud infrastructure. An important problem in this context, deals with finding an optimal virtual machine (VM) placement, minimizing costs, while at the same time, ensuring good system performance. Moreover, due to the fluctuations of demand and traffic patterns, it is crucial to dynamically adjust the VM placement scheme over time. It should be noted that most of the existing studies, however, dealt with this problem either by ignoring its dynamic aspect or by proposing solutions that are not suitable for a geographically distributed cloud infrastructure. In this paper, exact as well as heuristic solutions based on Integer Linear programming (ILP) formulations are proposed. Our work focuses also on the problem of scheduling the VM migration by finding the best migration sequence of intercommunicating VMs that minimizes the resulting traffic on the backbone network. The proposed algorithms execute within a reasonable time frame to readjust VM placement scheme according to the perceived demand. Our aim is to use VM migration as a tool for dynamically adjusting the VM placement scheme while minimizing the network traffic generated by VM communication and migration. Finally, we demonstrate the effectiveness of our proposed algorithms by performing extensive experiments and simulation.

The placement of surface-mounted components is an essential stage in printed circuit board assembly (PCBA). A reduction in production time of placement through efficient process planning will significantly increase the total yield of the whole line. A new approach to solving this problem is presented. This is based on a knowledge-based component placement system (CPS), which incorporates ready optimization algorithms. This approach is particularly suited to sophisticated but popular multi-head concurrent operation assembly machines. A case for going beyond just achieving an overall shortest travel distance in placement is also argued. A case study of this approach is presented.

A block placement representation called sequence pair was introduced by Murata. Many block placement algorithms that are based on sequence pairs use simulated annealing where the generation and evaluation of a large number of sequence pairs is required. This paper presents a new approach to evaluate a sequence pair based on computing longest common subsequence in a pair of weighted sequences. We present a very simple and efficient algorithm which has complexity lower than O(M^1.5), it is a significant improvement compared to the original O(M²) algorithm[1]. Experimental results show that our approach can estimate the area of a placement faster.

With the increase of circuit sizes and decrease of feature sizes it is expected that the overall performance of VLSI circuits will be more and more affected by signal propagation efficiency along interconnects. Wires can no longer be modeled as perfect conductors. Some electrical effects, previously considered as secondary, like for example parasitic loading introduced by wires, have to be taken into account at the layout design step. In this paper we address the problems of incorporating timing constraints into the placement and routing of integrated circuits. First, we introduce the timing models, formulate the problem and discuss graph models suitable for its analysis. Next, we give an overview of algorithms resulting in physical designs of improved performance in comparison to those whose objective is just the minimal layout.

The module placement and global routing problems are formulated as binary-valued optimization problems. The binary formulations allow these complex problems to be solved using specialized hardware or efficient mathematical software. The placement problem has been formulated as a hierarchical quadratic binary optimization problem, which is of a form that can be solved using a new neural network model. The global routing problem, with particular emphasis on the Sea-of-Gates and Custom Logic array design styles, has been formulated as a zero-one integer linear program, and solved using efficient zero-one optimization methods. Both of these approaches have produced highquality results on industrial circuits.

Global routing is an essential phase during the process of physical design of integrated circuits. Combinatorially, this problem amounts to a set of interdependent Steiner tree problems. Several versions of the problem are of importance in practical applications. All of them can be formulated as integer programs. Several such formulations have been investigated in the past, and different solution methods have been developed for different formulations.

In this paper we give an overview of integer program formulations of the global routing problem and their solution methods, and we introduce new concepts for solving this important combinatorial problem. Finally, we present integer program formulations that integrate placement with global routing.