An optimal algorithm for layout of CMOS functional cells, in the gate-matrix style, is proposed. A novel simultaneous graph partitioning technique, which facilitates concurrent partitioning of the p-part and n-part of...
详细信息
An optimal algorithm for layout of CMOS functional cells, in the gate-matrix style, is proposed. A novel simultaneous graph partitioning technique, which facilitates concurrent partitioning of the p-part and n-part of a CMOS cell, is introduced. The proposed algorithm lays out a given cell with n gates in O(log n ) rows, and runs in O( n log n ) time. Optimality of this bound is established by proving that there are instances of the problem that require ω (log n ) rows. The algorithm has been implemented and experimental results are included.
A method is presented for the joint source-channel coding optimization of a scheme based on the two-dimensional block cosine transform when the output of the encoder is to be transmitted via a memoryless binary symmet...
详细信息
A method is presented for the joint source-channel coding optimization of a scheme based on the two-dimensional block cosine transform when the output of the encoder is to be transmitted via a memoryless binary symmetric channel. The authors' approach involves an iterative algorithm for the design of the quantizers (in the presence of channel errors) used for encoding the transform coefficients. This algorithm produces a set of locally optimum (in the mean-squared error sense) quantizers and the corresponding binary codeword assignment for the assumed transform coefficient statistics. To determine the optimum bit assignment among the transform coefficients, the authors have used an algorithm based on the steepest descent method, which, under certain convexity conditions on the performance of the channel-optimized quantizers, yields the optimal bit allocation. Simulation results for the performance of this locally optimum system over noisy channels have been obtained, and appropriate comparisons with a reference system designed for no channel errors have been made. It is shown that substantial performance improvements can be obtained by using this scheme. Furthermore, theoretically predicted results and rate distortion-theoretic bounds for an assumed two-dimensional image model are provided.
The Kestrel Interactive Development System (KIDS), which provides automated support for the development of correct and efficient programs from formal specifications, is described. The system has components for perform...
详细信息
The Kestrel Interactive Development System (KIDS), which provides automated support for the development of correct and efficient programs from formal specifications, is described. The system has components for performing algorithm design, deductive inference, program simplification, partial evaluation, finite differencing optimizations, data type refinement, compilation, and other development operations. Although their application is interactive, all of the KIDS operations are automatic except the algorithm design tactics, which require some interaction at present. Dozens of programs have been derived using the system, and it is believed that KIDS could be developed to the point where it becomes economical to use for routine programming. To illustrate the use of KIDS, the author traces the derivation of an algorithm for enumerating solutions to the k-queens problem. The initial algorithm that KIDS designed takes about 60 minutes on a SUN-4/110 to find all 92 solutions to the 8-queens problem instance. The final optimized version finds the same solutions in under one second.
A novel application is presented of the tracking control technique to induction motor drive systems. By this technique, the position or the speed of the rotor can follow a preselected track (a time history of rotor po...
详细信息
A novel application is presented of the tracking control technique to induction motor drive systems. By this technique, the position or the speed of the rotor can follow a preselected track (a time history of rotor position or velocity). An algorithm for the design of the tracking controller is developed. The induction motor model and the controller are modified to allow the inclusion of the nonlinear modes in the system without excessive computations. A simple and realistic criterion for selecting the proper reference tracks during starting, speed control and braking is proposed. The controller developed, is tested on a full-size nonlinear analog simulator. All test results show the effectiveness of the scheme in position-tracking applications such as robotics and manipulators.
The concept ‘holistic algorithm’ is a MIMD paradigm for defining the highest level of parallelism possible in the design of an algorithm. In this paper we show how a general holistic algorithm may be implemented by ...
详细信息
The concept ‘holistic algorithm’ is a MIMD paradigm for defining the highest level of parallelism possible in the design of an algorithm. In this paper we show how a general holistic algorithm may be implemented by using the monitor synchronization concept. As an application a holistic vertex enumeration algorithm is designed based on a sequential predecessor.
Flexible assembly systems (FAS) promise to be an efficient processing approach for producing small and medium-sized batches of products. One vitally important element which affects the achievement of high performance ...
详细信息
Flexible assembly systems (FAS) promise to be an efficient processing approach for producing small and medium-sized batches of products. One vitally important element which affects the achievement of high performance by the FAS is its scheduling/dispatching component operating within the production planning and control system (PPCS). A detailed definition of the FAS scheduling process is given and key differences between this process and the classical simple job shop scheduling process are discussed. A mathematical model is developed for the minimize makespan problem, and it is shown that the problem is NP-complete, that it is one the most difficult problems in the class of decision problems that can be solved by polynomial time nondeterministic algorithm (NP). The design of heuristic solution procedures is also discussed.
This paper first presents a naive systolic algorithm for finding a closest point for each of n given points in linear time. Then, based on the algorithm, we propose linear-time systolic algorithms for the computation ...
详细信息
This paper first presents a naive systolic algorithm for finding a closest point for each of n given points in linear time. Then, based on the algorithm, we propose linear-time systolic algorithms for the computation of the visibility polygon and for the trapezoidal partition or triangulation of a polygonal region which may contain holes. The visibility problem among n vertical line segments in the plane is also solved.
By generalising problem solving techniques such as divide-and-conquer, dynamic programming, tree and graph searching, integer programming and branch-and-bound, a general problem solving algorithm is deduced. Various e...
详细信息
By generalising problem solving techniques such as divide-and-conquer, dynamic programming, tree and graph searching, integer programming and branch-and-bound, a general problem solving algorithm is deduced. Various examples of the use of this algorithm are given and its implementation on both sequential and parallel machines, such as the cosmic cube, is discussed.
designing efficient parallel algorithms in a message-based parallel computer should consider both time-space tradeoffs and computation-communication tradeoffs. In order to balance these tradeoffs and achieve the optim...
详细信息
designing efficient parallel algorithms in a message-based parallel computer should consider both time-space tradeoffs and computation-communication tradeoffs. In order to balance these tradeoffs and achieve the optimal performance of an algorith, one has to consider various design parameters such as the number of processors required and the size of partitions. In this paper, we demonstrate that, for certain data parallel algorithms, it is possible to determine these design parameters analytically. To serve as a basis for the discussions that follow, a simple model for the NCUBE hypercube computer is introduced. Using this model, we use two examples, array summation and matrix multiplication, to illustrate how their performance can be modeled. By optimizing these expressions, one is able to determine optimal design parameters which arrive at efficient execution. Experiments on a 64-node NCUBE verified the accuracy of the analytic results and are used to further support the discussions.
We investigate the relationship between algorithm construction and optimal decision processes. We provide a sufficient condition, a linear ordering over the experiment set, for when we can efficiently use an optimizat...
详细信息
暂无评论