In the past, government agencies played pivotal roles in the development of new technologies. For example, Internet is an outgrowth of the ARPAnet project sponsored by the Defense Advanced Research Projects Agency (DARPA) of the United States government. Recently, consortia of private industries, often in cooperation with government agencies, have entered into this picture. As a consequence, researchers in academia have shifted their attentions much more towards real-world applications. In the panel discussion, we first compare the traditional roles of funding agencies in the USA, EU, and Asia. We then focus on the new trends in this funding business in each of the three regions. We will examine why and how such shifts have been made and discuss the roles of funding agencies to be played in the coming years. In particular, we will attempt to search for future roles and new forms/ways of the funding agencies from the viewpoint of economic development driven by technology advancement.

The Logic Foundry is a system for the creation and integration of FPGA-based DSP systems. Recognizing that some of the greatest challenges in creating FPGA-based systems occur in the integration of the various components, we have developed a system that addresses the following four areas of integration: design flow integration, component integration, platform integration, and software integration. Using the Logic Foundry, a system can easily be specified, and then automatically constructed and integrated with system level software.

Introducing FPGA components into DSP system implementations creates an assortment of challenges across system architecture and logic design. Recognizing that some of the greatest challenges occur in the integration of the various components, we have developed a component architecture and an associated set of software tools, collectively called the Logic Foundry. Using the Logic Foundry, an FPGA-based DSP system can be easily constructed from pre-built components and implemented on a variety of back-end FPGA platforms. The resulting implementation can then be encapsulated and integrated into a variety of front-end software application environments. This paper develops the component architecture and integration capabilities of the Logic Foundry, and examines a number of application case studies that we have experimented with using the Logic Foundry.

A neural network based on relaxation dynamics is known to function as a maximum/minimum detector. In such a network, it is necessary to design an adequate energy function to be minimized for the derivation of network dynamics. However, even if the feedback connections are well-tuned, the detection greatly depends on the initial states of neural cells. For example, under the condition that all or some of the maximal/minimal values in a task are the same, certain cell states may not change on a saddle point in the network dynamics. We consider the simplest case of a 2-value minimum defection task. We show how a module-based neural network with "redundant" architecture is used in an attempt to solve such problems as the initial-value dependence and deadlocking.

We present a very fast area router for multichip module (MCM) design. Given a set of nets and a routing area, the router repeatedly selects two layers from top to bottom and routes as many nets as possible until all the nets are routed. The router uses a line sweep technique and a simple net selection algorithm. By employing efficient data structures and a novel priority scheme, the routing can be completed in time almost proportional to the size of the routing area. When applied to the benchmark circuits, the proposed router generated comparable routing results 23 times faster on the average than the previously reported fastest and effective router. When compared with the previously reported best routing result achiever, our router produced slightly worse results but ran 102 times faster on the average. Its effectiveness and ultra fast computation time make this router ideally suited for the next generation of large scale MCM designs.

Article A simple and effective greedy multilayer router for MCMs Share on Authors: Young-Jun Cha Electronics and Telecommunications Research Institute, Taejon, Korea Electronics and Telecommunications Research Institute, Taejon, KoreaView Profile , Chong S. Rim Department of Computer Science, Sogang University, Seoul, Korea and Electrical Engineering Department, University of Maryland, College Park, MD Department of Computer Science, Sogang University, Seoul, Korea and Electrical Engineering Department, University of Maryland, College Park, MDView Profile , Kazuo Nakajima Electrical Engineering Department, University of Maryland, College Park, MD Electrical Engineering Department, University of Maryland, College Park, MDView Profile Authors Info & Claims ISPD '97: Proceedings of the 1997 international symposium on Physical designApril 1997 Pages 67–72https://doi.org/10.1145/267665.267686Online:01 April 1997Publication History 10citation161DownloadsMetricsTotal Citations10Total Downloads161Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We present a new min-cut based placement algorithm for large scale sea-of-gates arrays. In the past all such algorithms were developed based on a single local optimization function, called the sequential cut line objective function. Our algorithm incorporates global objective functions into this traditional framework of min-cut placement. In particular, we introduce a new global objective function based on the congestions for cut lines and use it for the selection of their sequence. We also use the total cut value objective function in the determination of the sizes and connectivities of clusters that are to be used in the early stages of min-cut partitioning. The incorporation of such global objective functions yields additional reductions of wire congestions in the entire as well as local chip areas. With the automatic selection and use of such clusters and a cut line sequence, our algorithm can produce, in a short time and at a low cost, final placement results that achieve the 100% completion of wiring on chips of fixed sizes. This has led to its successful production use, having generated more than 400 CMOS sea-of-gates array chips of 1.5 K to 150 K raw gates.>

In an approach recently proposed for the yield enhancement of programmable gate arrays (PGA's), an initial placement of a circuit is first obtained using a standard technique such as simulated annealing on a defect-free PGA. In the next step, this placement is reconfigured so that the circuit is mapped onto the defect-free portion of a defective PGA chip with the same architecture. We first formulate the reconfiguration aspect of this approach as a problem of shifting pebbles on a graph. We present efficient reconfiguration algorithms for this pebble shift problem. Using these algorithms as heuristics, we develop a yield enhancement system not only for PGA's, but also for programmable Wafer Scare Integrated (WSI) processor arrays. We evaluate the heuristic algorithms using the measures of routability and total wire length of the reconfigured placement of the circuit. Based on this evaluation, we establish proper reconfiguration strategies.>

We introduce a new model for over-the-cell channel routing with three layers. The model consists of two channels and the routing area over a cell row between them. Three and two layers are available for routing in the channels and the over-the-cell routing area, respectively. We formulate the problem of over-the-cell routing as that of channel routing with additional constraints. Based on this formulation, we present an efficient over-the-cell routing algorithm that attempts to minimize the sum of channel densities of the trunks that remain in the channel. The effectiveness of our model and algorithm is demonstrated by our experimental results on industrial sea-of-gates array chips and a well-known benchmark circuit.>

An approach to yield enhancement of programmable array chips by logical restructuring of circuit placements was recently proposed by Kumar et al. (1991). and a graph model for its reconfiguration aspect was later introduced by Narasimhan et al. (1991). Using this model and a new cost measure, we present a complete yield enhancement system. We implement two reconfiguration algorithms on it, evaluate their performances, and propose good reconfiguration strategies.>

The authors propose an approach to an over-the-cell channel routing problem using a model that consists of two channels and the routing area over a cell row between them. Three and two layers are available for routing in the channels and the over-the-cell routing area, respectively, The problem is decomposed into two phases: over-the-cell routing and channel routing. The authors formulate the problem in the first phase as that of channel routing with additional constraints. Based on this formulation, they present an efficient over-the-cell routing algorithm. The effectiveness of the approach is demonstrated by experimental results on sea-of-gates array chips.>

Abstract Let S be a family of arcs on a circle. A graph G = (V,E) is called a circular‐arc overlap graph for S if (i) there is a one‐to‐one correspondence between V and S and (ii) two vertices in V are adjacent if and only if the corresponding arcs in S intersect but neither one of them contains the other. In this article, we present two polynomial time algorithms on circular‐arc overlap graphs. Given a circular‐arc overlap graph in the form of a family of n arcs, the first algorithm obtains a maximum independent set in O(n2) time and the second one finds a maximum clique in O(n5) time.

To obtain a minimum width cell layout of a static CMOS circuit in the Uehara-vanCleemput (1981) style the circuit is often modeled as a pair of dual series-parallel multigraphs. The problem then reduces to finding a minimal number of edge-disjoint dual paths that cover the pair of graphs. Presented is an O(l) time heuristic algorithm for this problem, where l is the number of literals in an input prefix logic expression. It utilises the decomposition tree structure of the dual multigraphs. The algorithm produces optimal solutions to all the examples available in the literature. The algorithm is able to process very complicated logic expressions and almost always produces cell layouts of minimum width in less than a second.>

Abstract Let F = {I1, I2,…,In} be a finite family of closed intervals on the real line. Two intervals Ij and Ik in F are said to overlap each other if they intersect but neither one of them contains the other. A graph G = (V, E) is called an overlap graph for F if there is a one‐to‐one correspondence between V and F such that two vertices in V are adjacent to each other if and only if the corresponding intervals in F overlap each other. In this paper, we present two efficient algorithms for finding maximum cliques of an overlap graph when it is given in the form of a family of n intervals. The first algorithm finds a maximum clique in O (n. log n + Min {m, n‐ ω}) time, where m is the number of edges and ω is the size of a maximum clique, respectively, of the graph. The second algorithm generates all maximum cliques in O (n ‐ log n + m + γ) time, where γ is the total sum of their sizes.

The problem of embedding a graph in the plane with the minimum number of edge crossings arises in some circuit layout problems. It has been known to be NP-hard in general. Recently, in the area of book embedding, this problem was shown to be NP-hard even when the vertices are placed on a straight line l. The authors show that the problem remains NP-hard even if, in addition to these constraints, the positions of the vertices on l are predetermined.>

The vertex- (respectively, edge-) deletion graph bipartization problem is the problem of deleting a set of vertices (respectively, edges) from a graph so as to make the remaining graph bipartite. This paper first shows that the vertex-deletion graph bipartization problem has a solution of size k or less if and only if the edge-deletion graph bipartization problem has a solution of size k or less, when the maximum vertex degree is limited to three. This immediately implies that (1) the vertex-deletion graph bipartization problem is NP-complete for cubic graphs, and (2) the minimum vertex-deletion graph bipartization problem is solvable in polynomial time for planar graphs when the maximum vertex degree is limited to three. It is then proved that the vertex-deletion graph bipartization problem is NP-complete for planar graphs when the maximum vertex degree exceeds three. Using this result, it is finally shown that the via minimization problem, which arises in the design of integrated circuits and printed circuit boards, is NP-complete even when the maximum “junction” degree is limited to four.

The authors analyze the computational complexity of the constrained via minimization problem. Given an already routed circuit, the problem is to find a minimum cardinality set of vias for which a valid layer assignment exists using only two layers. The authors first prove that the corresponding decision problem is NP-complete. They then show that it remains NP-complete even if one or more of the following restrictions are imposed: (1) the input layout must conform to a rectangular grid; (2) vias are restricted to lie at junctions which existed in the input layout; and (3) the maximum junction degree is limited to six or more.>

In the past, several heuristic algorithms were developed for the topological via minimization problem. It was very recently shown to be NP-hard even for the two-layer channel routing case with two-terminal nets only. The authors show that if no local net exists in a channel, this problem is solvable in O(kn/sup 2/) time even for k layers, where n is the number of two-terminal nets. As an extension of this case, they consider the problem for the case of k-layer circular channel routing in which no local net exists and present an O(n/sup 2k+1/) time algorithm.>

A new algorithm is presented for finding a maximum independent set of a circular-arc graph. When the graph is given in the form of a family of n arcs, our algorithm requires only $O(n \cdot \log n)$ time and $O(n)$ space. Furthermore, if the endpoints of the arcs are already sorted, it runs in $O(n)$ time. This algorithm is time- and space-optimal to within a constant factor.

This paper describes a graph theoretic algorithm which, given a particular layout, finds a layer assignment that requires the minimum number of vias. The time complexity of the algorithm is Ο(n3) where n is the number of routing segments in the given layout. Unlike previous algorithms, this algorithm does not require the layout to be grid based and places no constraints on the location of vias or the number of wires that may be joined at a single junction. The algorithm yields globally optimum results when the maximum junction degree is limited to three and has been fully implemented.

The fault diagnosability problem is the problem of computing the maximum number of faulty units which a system can tolerate without losing its capability of identifying all such faulty units. We study this problem for the model introduced by Barsi, Grandoni, and Maestrini [2]. We present a new characterization of the model, and develop an efficient diagnosability algorithm for a system in this model.

In the theory of t-fault-diagnosable systems, one first chooses a set of diagnostic tests, then seeks the results of these tests, and finally proceeds to use the test results to identify the faulty units assuming that the number of faulty units does not exceed t. Nakajima was the first to suggest a departure from this practice. He proposed to adaptively choose the tests and to seek their results until one can identify a fault-free unit. This fault-free unit may then be used as a tester to identify all faulty units. In this paper, we exploit this idea fully and show that one needs the results of at most (n + 2t −2) adaptive tests to identify all faulty units in a t-fault-diagnosable system with n units. The impact of the applications of this idea to the various models and diagnosis algorithms is examined.

This paper describes the traffic assistance service system that has been developed as a standard operator position system applicable to ESS and is employed in a variety of NEC's telephone switching systems. To provide services of various kinds of semiautomatic calls, it is important that operator position system is not only a cost-saving system but also has a wide range of flexibility. For this reason, this operator position system has been developed as an operator position system which is theoretically independent of the main switching system and is employing a variable function share control system and an optimum modularity of both hardware and software. Also, as the operators attend their positions continuously during their work time, it is important that various human engineering factors are incorporated in the operator position system. In this regard, the following factors have been introduced in this operator position system; equalization of operators' work loads and a call handling system which depend on the operator's will, simplification of call handling procedures inclusive of automatization of some operations, plasma display provision designed with operator's visual sense taken into consideration, and employment of operator console of such physical construction that is based on the movable range of the human body and on easiness of the operator's work performance.