ICS has a technical report series, three academic departments and 3 ORUs associated with it that each generate new information and knowledge.
We show that any algorithm that maintains the connected components of a digital image must take Ω(log n/log log n) time per change to the image. The problem can be solved in O(log n) time per change using dynamic planar graph techniques. We discuss applications to computer Go and other games.
Improving on a recent breakthrough of Sharir, we show how to find two circular disks of minimum radius covering a set of points in the Euclidean plane, in randomized expected time O(n log^2 n).
In interactive behavioral synthesis, the designer can control the design process at every stage, including modifying the schedule of the design to improve its performance. In this report, we present a methodology for performance optimization in interactive behavioral synthesis. Also proposed in this report are several quality metrics and hints that can assist the user in utilizing the proposed methodology. When the user is optimizing the performance of the design, one important decision is the selection of a clock period. We have developed an algorihm to estimate the effect of different clock periods on the execution time of the design. This algorithm can be used to facilitate clock period selection by the user in order to optimize the performance of the design. We have tested our methodology on several benchmarks. The experimental results support the proposed methodology on several benchmarks. The experimental results support the proposed methodology by demonstrating an average improvement of 46.2% in design performance.
In order to reduce the design cost of pipelined systems, resources may be shared by operations within and across different pipe stages. In order to maximize resource sharing, a crucial decision is the selection of a clock period, since a bad choice can adversely affect the performance and cost of the design. In this report, we present an algorithm to select a clock period that attempts to minimize design area while satisfying a given throughput constraint. Experimental results on several examples demonstrate the quality of our selection algorithm and the benefit of allowing resource sharing across pipe stages.
An important decision in synthesizing a hardware implementation from a behavioral description is selecting the clock period to schedule the datapath operations into control steps. Prior to scheduling, most existing behavioral synthesis systems either require the designer to specify the clock period explicitly or require that the delays of the operators used in the design be specified in multiples of the clock period. An unfavorable choice of the clock period could result in operations being idle for a large portion of the clock period, and consequently, affect the performance of the synthesized design. In this paper, we demonstrate the effect of clock slack on the performance of designs and present an algorithm to find a slack-minimal clock period. We prove the optimality of our method and apply it to several examples to demonstrate its effectiveness in maximizing design performance.
Software architectures shift the focus of developers from lines-of-code to coarser-grained architectural elements and their overall interconnection structure. Architecture description languages (ADLs) have been proposed as modeling notations to support architecture-based development. There is, however, little consensus in the research community on what is an ADL, what aspects of an architecture should be modeled in an ADL, and which of several possible ADLs is best suited for a particular problem. Furthermore, the distinction is rarely made between ADLs on one hand and formal specification, module interconnection, simulation, and programming languages on the other. This paper attempts to provide an answer to these questions. It motivates and presents a definition and a classification framework for ADLs. The utility of the definition is demonstrated by using it to differentiate ADLs from other modeling notations. The framework is also used to classify and compare several existing ADLs. One conclusion is that, although much research has been done in this area, no single ADL fulfills all of the identified needs.
We show that for any edge-weighted graph G there is an equivalent graph EG such that the minimum spanning trees of G correspond one-for-one with the spanning trees of EG. The equivalent graph can be constructed in the time O(m + n log n) given a single minimum spanning tree of G. As a consequence we can count the minimum spanning trees of G in time O(m + n^2.376), generate a random minimum spanning tree in time O(mn), and list all minimum spanning trees in time O(m + n log n + k) where k denotes the number of minimum spanning trees generated. We also discuss similar equivalent graph constructions for shortest paths, minimum cost flows, and bipartite matching.
We use Mathematica to construct zonotopes and display zonohedra.
We consider the problem of finding pairs of vertex-disjoint paths in a DAG, either connecting two given nodes to a common ancestor, or connecting two given pairs of terminals. It was known how to find a single pair of paths, for either type of input, in polynomial time. We show how to find the k pairs with shortest combined length, in time O(mn + k). We also show how to count all such pairs of paths in O(mn) arithmetic operations. These results can be extended to finding or counting tuples of d disjoint paths, in time O(mn^(d-1 + k). We give further results on finding the subset of the DAG involved in pairs of disjoint paths, and on finding disjoint paths in linear space.