18451647
Optimal circuit clustering for delay minimization under a more general delay model
This paper considers the area-constrained clustering of combinational circuits for delay minimization under a more general delay model, which practically takes variable interconnect delay into account. Our delay model is particularly applicable when allowing the back-annotation of actual delay information to drive the clustering process. We present a vertex grouping technique and integrate it with the algorithm (Rajaraman and Wong, 1995) such that our algorithm can be proved to solve the problem optimally in polynomial time.
2339232
Maze routing with OPC consideration
47136995
Routing for symmetric FPGAs and FPICs
A new class of routing structures with fixed orthogonal wire segments and field programmable switches at the intersections of the wire segments is proposed. In comparison with the conventional two-dimensional field-programmable gate array (FPGA) routing structure, this class of routing structures has the advantage of using a smaller number of active programmable switches. An existing field-programmable interconnect chip (FPIC) routing structure can be included as a special case in our class of routing structures. Using a probabilistic model, we prove that complete routing can be achieved with a high degree of probability in a routing structure of this class in which the number of tracks in each channel approaches the lower bound asymptotically. We present a sequential routing algorithm based on the solution of the single net routing problem. We take into account the delay introduced by the active programmable switches on a routing path and formulate the single net routing problem as a node-weighted Steiner minimum tree (NWSMT) problem in a bipartite graph G. Since our single net routing problem is NP-complete, a polynomial time approximate algorithm is proposed. We prove that our single net routing algorithm produces an optimal solution for some special classes of bipartite graphs. In general, the solution obtained by our algorithm bas a performance bound of min{/spl Delta/(V/Z), |Z|-1}. Experimental results for several industrial circuits show a reduction of up to 41% in the number of active programmable switches when compared with corresponding results for the conventional FPGA routing structure.
195349922
Routing for symmetric FPGAs and FPICs
30326495
Performance-driven channel pin assignment algorithms
In this paper we consider two channel pin assignment problems which take circuit performance into account. The first one is the module implementation selection problem. We are given a net span bound for each critical net and each module has several possible placements of its pins. Our objective is to minimize channel density while satisfying net span constraints. We proved that this problem is NP-complete. For the case when each module has at most 2 pin placements, the problem can be transformed to the 2-SAT problem and hence is polynomial time solvable. We present a heuristic based on this algorithm to solve the general case. The second problem we consider is the module shifting problem. We are given a set of modules whose relative ordering is fixed on each side of the channel but their exact positions are not fixed. We present a polynomial time algorithm to test the feasibility of satisfying the net span constraints by shifting the modules. The algorithm is based on formulating the problem as a special integer linear programming problem which is solvable in polynomial time. We also extend our algorithms to handle multiple channels. >
33246096
Optimal net assignment
We study in this paper the net assignment problem subject to the capacity constraint, selection constraint and routing constraint. Given two adjacent channels separated by a cell row, and a set of nets in each of the two channels, this problem is to assign to the cell row a subset of nets in each channel such that without violating any given constraint, the sum of the remaining densities of the two channels is minimized. The capacity constraint requires the density caused by the nets, which are assigned to the cell row, to be no more than a user-specified number k, where k is no more than the number of tracks available for routing over that cell row. The selection constraint specifies in each channel the subset of nets which are candidates to be assigned to the cell row. The routing constraint requires each net to be either completely assigned to the cell row or to stay in its channel. This problem can find its application in modeling a practical over-the-cell routing problem in which the whole region over the cell row is two-layer routable for the nets in the two adjacent channels. We present an optimal algorithm to solve this problem and provide experimental results to support our algorithm. >
28214269
Active rule processing in the BioCompose database
BioCompose is an object-relational database query tool that runs on top of any relational database and provides an intelligent and complete object-relational interface to the user. Unlike the traditional approach, which is completely table driven, queries in BioCompose are structured along the lines of natural language and sentences. In BioCompose, the database server continuously monitors the triggers and integrity constraints which are expressed as logical rules and are evaluated based on incoming events which include real time events, value events, transaction events, abstract events, and message events. The paper presents a novel approach that compiles triggers and integrity constraints into an asynchronous network to minimize the rule evaluation effort under different kinds of events.
13299166
An Interpolated Volume Model for Databases
In this paper we present a volume data model amenable to querying volumes in databases. Unlike most existing volume models, which are directed towards specific applications (notably, volume displaying) and are therefore directed towards executing with the greatest possible efficiency a small set of operations, we are interested in defining a volume algebra through which generic query conditions can be composed.
206985371
Framework and network based multimedia object management environment
Because multimedia objects are becoming more prevalent, on ever increasing volume, inventing an efficient multimedia object management environment is a matter of increasing urgency. In recognition of this crisis, we developed the multimedia object management environment (MOME) that includes a suite of tools such as the Vortex framework, and network file indexer (NFI). MOME also includes a fully featured graphical user interface for maximum user control and flexibility. With meta data, it automatically generates indexes and paths for different types of multimedia objects and allows users to quickly find what they are looking for. In this paper, we address the background, architecture, and performance of MOME in detail.
15371718
Automatic Chromosome Classification Using Medial Axis Approximation and Band Profile Similarity
Automated chromosome classification is an essential task in cytogenetics and has been an important pattern recognition problem. Numerous attempts were made in the past to characterize chromosome to perform clinical and cancer cytogenetics research. It is important to determine optimum features and develop feature extraction schemes for chromosome classification. In this paper we propose novel approaches for medial axis determination and profile matching of human chromosome. The medial axis determination plays a critical role for precise and complete extraction of band patterns of chromosomes. The features of the band profile obtained along the axis are then used in the classification process. In particular, the medial axis is obtained by simple cross-section analysis and the classification is accomplished through iterative pairing of band profiles. According to the experimental results, the developed automatic system can efficiently extract band profiles of the chromosomes along their medial axes, and satisfactory chromosome classification results can be obtained.
10441616
Automatic Gait Optimization with Gaussian Process Regression
Gait optimization is a basic yet challenging problem for both quadrupedal and bipedal robots. Although techniques for automating the process exist, most involve local function optimization procedures that suffer from three key drawbacks. Local optimization techniques are naturally plagued by local optima, make no use of the expensive gait evaluations once a local step is taken, and do not explicitly model noise in gait evaluation. These drawbacks increase the need for a large number of gait evaluations, making optimization slow, data inefficient, and manually intensive. We present a Bayesian approach based on Gaussian process regression that addresses all three drawbacks. It uses a global search strategy based on a posterior model inferred from all of the individual noisy evaluations. We demonstrate the technique on a quadruped robot, using it to optimize two different criteria: speed and smoothness. We show in both cases our technique requires dramatically fewer gait evaluations than state-of-the-art local gradient approaches.