The problem of scheduling pairs of aircraft for simultaneous landing onto very closely spaced parallel runways is studied. The pair scheduling problem and its generalization group scheduling problem for simultaneous landing onto parallel runways are formulated and shown to be NP-hard, in general. A genetic pairing scheduler algorithm is developed, capable of handling a wide range of constraints, and used in a real-time human-in-the-loop simulation that was carried out to study the operational concept. Experimental data from these simulations and an extensive set of stress tests are presented and analyzed. Results indicate that while the problem is NP-hard in general, practical instances of the algorithm are not necessarily very hard to solve. As such, the proposed algorithm succeeded in finding and suggesting aircraft pairs that met all the problem constraints and thus were accepted by the controllers in over 97% of the cases. High solution quality, scalable runtime, and flexibility of the proposed algorithm in handling different constraints suggest that it is a suitable candidate for use in a real-time application.

In this paper, we investigate reducing the power consumption of a synchronous digital system by minimizing the total power consumed by the clock signals. We construct activity-driven clock trees wherein sections of the clock tree are turned off by gating the clock signals. Since gating the clock signal implies that additional control signals and gates are needed, there exists a tradeoff between the amount of clock tree gating and the total power consumption of the clock tree. We exploit similarities in the switching activity of the clocked modules to reduce the number of clock gates. Assuming a given switching activity of the modules, we propose three novel activity-driven problems: a clock tree construction problem, a clock gate insertion problem, and a zero-skew clock gate insertion problem. The objective of these problems is to minimize the system's power consumption by constructing an activity-driven clock tree. We propose an approximation algorithm based on recursive matching to solve the clock tree construction problem. We also propose an exact algorithm employing the dynamic programming paradigm to solve the gate insertion problems. Finally, we present experimental results that verify the effectiveness of our approach. This paper is a step in understanding how high-level decisions (e.g., behavioral design) can affect a low-level design (e.g., clock design).

A linear arrangement problem, called the minmax mincut problem, emerging from circuit design is investigated. Its input is a series-parallel directed hypergraph (SPDH), and the output is a linear arrangement (and a layout). The primary objective is to minimize the longest path, and the secondary objective is to minimize the cutwidth. It is shown that cutwidth D, subject to longest path minimization, is affected by two terms: pattern number k and balancing number m. Also, k and m are both lower bounds on the cutwidth. An algorithm, running in linear time, produces layouts with cutwidths $D \leq 2(k+m)$. There exist examples with $k=\Omega (N)$, where N is the number of vertices; however, m is always O(log N). We show that every SPDH, after $local\ logic\ resynthesis$ (specifically, after reordering the serial paths), can be linearly placed with cutwidth D=O(log N). Simultaneously, its dual SPDH can be linearly placed with the same vertex order and with cutwidth D=O(log N). Therefore, after local resynthesis the area can be reduced by a factor of N/log N. Application to gate-matrix layout style is demonstrated.

Sleep mode operation and exploiting it to minimize the average power consumption are o f g r e at importance.In this paper, we formulate the memory segmentation/partitioning problem to exploit sleep mode operation and show that the problem is NP-complete.We present polynomial time algorithms for special classes of the problem.Some generalizations of the problem are discussed.Preliminary experiments are c onducted to show the eectiveness of the algorithms and applicability of the approach.The experimental data con rm that a careful partitioning allows up to 40% more sleep time which could be exploited to minimize the average power consumption.Directions for further research in this area a r e presented.

Partitioning of a system to maximize exploitable sleep time for low-power synthesis is discussed. The motivation is to deactivate the memory refresh circuitry, apply power down or disable the clock signals during the inactive periods of operation of circuit elements, and thus minimize the power consumption. Since it is impractical to have a separate set of control signals for each circuit element (otherwise, the control itself would consume a lot of power), it is advisable to partition a circuit based on the activity patterns of its elements so that the partitions can be switched into sleep mode for long periods of time. In this paper, we formulate this partitioning problem and show that it is NP-hard. We present Geo-Part, a geometric partitioning heuristic for this problem. An efficient implementation of Geo-Part using segment tree data structure is discussed. Experimental results are encouraging.

In this paper we investigate activity-driven clock trees to reduce the dynamic power consumption of synchronous digital CMOS circuits. Sections of an activity-driven clock tree can be turned on/off by gating the clock signals during the active/idle times of the clocked elements. We propose a method of obtaining the switching activity patterns of the clocked circuits during the high level design process. We formulate three novel activity-driven problems. The objective of these problems is to minimize system's dynamic power consumption. We propose an approximation algorithm based on recursive matching to solve the clock tree construction problem. We solve the gate insertion problems with an exact algorithm employing the dynamic programming paradigm. Finally, we present experimental results that verify the effectiveness of our approach. Our work in this paper is a step in understanding how high level decisions (e.g. behavioral design) can affect a low level design (e.g. clock design).

One of the main objectives in the process of mapping a digital circuit onto a LUT-based FPGA structure is minimizing the total number of lookup tables needed to implement the circuit. This will increase the size of the circuit that can be implemented using the available FPGA structure. In this paper, we show that even restricted cases of the lookup-table minimization for FPGA technology mapping are NP-complete (even when K is a small constant), and that it can be solved optimally for all values of K on a tree input in O(min{nK, nlogn}) time where n is the number of nodes in the network and K is the input capacity of the LUT's. Based on our algorithm for trees, we present a polynomial time heuristic algorithm for general Boolean networks. Experimental results confirm substantial decrease on the number of LUT's on a number of MCNC logic synthesis benchmarks compared to the algorithms that allow no or just local exploitation of Boolean properties of the circuit. We obtain 10% to 80% improvement on the number of LUT's compared to the previous algorithms (even though we allow very limited operations, e.g., we do not exploit Boolean properties of the circuits or decompose nodes).>