Technische Berichte

Stichworte: 
   Autoren: 
              

Sonderforschungsbereich 124, VLSI-Entwurfsmethoden und Parallelität

• Thomas Chadzelek and Günter Hotz. Analytic machines. Technical Report 12/97, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, December 1997. (Gzipped PostScript, 10 pages, 69852 bytes)

  In this paper we present some results about analytic machines regarding the power of computations over Q or R, solutions of differential equations and the stability problem of dynamical systems. We first explain the machine model, which is a kind of sf Blum-Shub-Smale machine enhanced by infinite convergent computations. Next, we compare the computational power of such machines over the fields Q and R showing that finite computations with real numbers can be simulated by infinite converging computations on rational numbers, but the precision of the approximation is not known during the process. Our attention is then shifted to ordinary differential equations (ODEs), dynamical systems described by ODEs and the undecidability of a class of stability problems for dynamical systems.

• Günter Hotz and Bin Zhu. Verifying parameterized recursive circuits using semantics-preserving transformations of nets. Technical Report 11/97, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1997. (Gzipped PostScript, 34 pages, 156226 bytes)

• Günter Hotz and Bin Zhu. Applying Calculus of Nets to Hardware Verification Using Higher Order Logic. Technical report, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), 1996.

• Günter Hotz and Bin Zhu. Formal Hardware Verification Based on Semantics-Preserved Transformations of Nets. Technical report, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), 1996.

• Günter Hotz and Bin Zhu. Verifiable Synthesis by Using Semantics-Preserved Transformations of Nets. Technical report, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), 1996.

• G. Hotz and H. Wu. On the arrangement complexity of uniform trees. Technical Report SFB124-95-05, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), 1995. (Gzipped PostScript, 16 pages, 61466 bytes)

• P. Uppaluri, U. Sparmann, and I. Pomeranz. On minimizing the number of test points needed to achieve complete robust path delay fault testability. Technical Report SFB124-95-08, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), 1995. (Gzipped PostScript, 8 pages, 82654 bytes)

  Recently, Pomeranz and Reddy [7], presented a test point insertion method to improve path delay fault testability in large combinational circuits. A test application scheme was developed that allows test points to be utilized as primary inputs and primary outputs during testing. The placement of test points was guided by the number of paths and was aimed at reducing this number. Indirectly, this approach achieved complete robust path delay fault testability in very low computation times. In this paper, we use their test application scheme, however, we use more exact measures for guiding test point insertion like test generation and RD fault identification. Thus, we reduce the number of test points needed to achieve complete testability by ensuring that test points are inserted only on paths associated with path delay faults that are necessary to be tested and that are not robustly testable. Experimental results show that an average reduction of about 70 % in the number of test points over the approach of [7] can be obtained.

• B. Becker, R. Hahn, J. Hartmann, and U. Sparmann. On the testability of iterative logic arrays. Technical Report SFB124-94-04, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), 1994. (Gzipped PostScript, 23 pages, 89086 bytes)

  The problem of detecting single cellular faults in arbitrarily large one-dimensional, unilateral, combinational iterative logic arrays (= ILAs) is considered. Fault patterns (= FPs) of the ILA's basic cell are introduced to characterize any cellular fault. Testability properties like (full, partial) testability, redundancy, test complexity of FPs are studied. Based on this analysis we prove that only two test complexity classes exist: The minimum size of a complete test set of an ILA is either constant - in this case the ILA is called C-testable - or linear in the length of the ILA. Furthermore, depending on the type of the FP that is considered new efficient algorithms for the determination of the test complexity and the construction of complete test sets are presented. In particular, we reduce the exponential worst case complexity of the construction given in [Fri73] to a polynomial worst case bound (measured in the size of the function table for the basic cell).

• U. Sparmann, D. Luxenburger, K.-T. Cheng, and S.M. Reddy. Fast identification of robust dependent path delay faults. Technical Report SFB124-94-08, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), 1994. (Gzipped PostScript, 11 pages, 112708 bytes)

  Recently, it has been shown in [LSBS93] and [CC93] that in order to verify the correct timing of a manufactured circuit not all of its paths need to be considered for delay testing. In this paper, a theory is developed which puts both of the above papers in a common framework, thus allowing for a better understanding of their relation. In addition, we consider the computational problem of identifying large sets of such not-necessary-to-test paths. Since the approach of [LSBS:93] can only be applied for small scale circuits, we develop a new algorithm which trades quality of the result against computation time, and allows to handle large circuits with tens of millions of paths. Experimental results show that enormous improvements in running time are only paid for by a small decrease in quality.

• B. Becker, R. Drechsler, and P. Molitor. On generation of area time optimal testable adders. Technical Report SFB124-93-03, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1993.

• T. Burch, J. Hartmann, G. Hotz, M. Krallmann, U. Nikolaus, S.M. Reddy, and U. Sparmann. Hit - a hierarchical environment for interactive test engineering. Technical Report SFB124-93-20, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), 1993. (Gzipped PostScript, 14 pages, 91772 bytes)

  Conventional tools for test generation and fault simulation appear to the test engineer as black boxes which neither communicate their results in a convenient way, nor allow for any interactive guidance by the test engineer. In contrast, the HIT system presented in this paper supports interactive test engineering, thus combining the power of gate level test generation algorithms with the high level knowledge of the test engineer. Since the HIT system has been integrated into a hierarchical design system (CADIC), the results of test tools can be visualized at the hierarchical circuit specifications given by the designer. Based on this visualization, the critical, untestable areas of the circuit can be easily located. Additionally, the test engineer is supplied with flexible test tools, which allow him to actively guide the test development process. Thus, he can easily apply module specific test strategies or `communicate' his high level knowledge about the functionality of the overall circuit to speed-up test generation and redundancy identification. An application example shows that with simple strategies for interactive test engineering the results of test generation can be improved dramatically.

• G. Hotz. Suchbäume und und Suchgraphen bei Markoffquellen. Technical Report SFB124-93-11, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1993.

• G. Hotz and J. Sellen. On algebraic computation tree and Betti numbers. Technical Report SFB124-93-10, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1993.

• P. Molitor and Ch. Scholl. Mehrstufige Logiksynthese unter Ausnutzung von Symmetrien und nichttrivialen Zerlegungen. Technical Report SFB124-93-02, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1993. (Gzipped PostScript, 166 pages, 364543 bytes)

• P. Molitor, U. Sparmann, and D. Wagner. Two-layer wiring with pin preassignments is easier if the power supply nets are already generated. Technical Report SFB124-93-01, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), 1993. (Gzipped PostScript, 6 pages, 79664 bytes)

  We examine the constrained via minimization problem with pin preassignments (CVMPP) which arises in connection with hierarchical physical synthesis. Let A be a circuit composed of subcircuits B, C, D, ... . Assume that the placement and routing phase together with the 2-layer wiring of the subcircuits, and the placement and routing phase without the 2-layer wiring of A are completed. CVMPP is the problem of finding a 2-layer wiring delta _A of A which is induced by the 2-layer wirings of the subcircuits and which contains a minimal amount of vias on this condition. First, we show that CVMPP is NP-complete. In the case that the wiring of the power supply nets has already been generated we present a polynomial time algorithm solving CVMPP.

• B. Becker, R. Drechsler, and P. Molitor. On the implementation of an efficient performance driven generator for conditional-sum adders. Technical report, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1992.

• Björn Schieffer. Fast navigation in hierarchical circuits. Technical Report SFB124-92-14, Sonderforschungsbereich 124 VLSI Entwurfsmethoden und Parallelität, 1992. (Gzipped PostScript, 32 pages, 74010 bytes)

  In this paper, three demands of a good logic simulator for hierarchical circuits are postulated: stack oriented signal assignment, hierarchical circuit representation and linear runtime. It is shown that the intuitive idea of a hierarchical simulator does not hold condition 3 having a runtime of Theta (n²) in the circuit size. May this be improved or is there a contradiction in these conditions? Not in the way that there are two conflicting groups, as for each pair of these conditions an algorithm may be presented. But it is shown that there is no way to fulfill all of them at once!

• U. Sparmann. On-line error detection in fast adders by residue codes. Technical report, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1992.

• H. Wu. On the Test Complexity of Uniform Tree Circuits. Technical Report SFB124-92-06, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1992.

• B. Becker and P. Molitor. A performance driven generator for efficient testable adders. Technical Report SFB124-91-14, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, October 1991. Erschienen als extended abstract auf der EURODAC92.

• R. Drefenstedt and T. Walle. Implementierung eines effizient testbaren Gleitkommaaddierers auf einer kommerziellen Sea-of-Gate Struktur. Technical Report SFB124-91-10, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1991.

• U. Becker and G. Hotz. Foldingfree covering and graph embeddings. Technical Report SFB124-90-01, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1990. 17 Seiten. Erscheint in dem Sonderband der Abhandlungen des Mathematischen Seminares der Universität Hamburg anlä\3lich des 300-ten Geburtstages der Mathematischen Gesellschaft zu Hamburg.

• P. Fischer and H.U. Simon. Two-dimensional separation problem. Technical Report SFB124-90-04, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1990. 22 pages.

• J. Hartmann. On deterministic versus probabilistic testing. Technical Report SFB124-90-02, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1990. 24 pages.

• M. Kaufmann, P. Molitor, and W. Vogelgesang. Performance driven k-layer wiring. Technical Report SFB124-90-14, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1990.

• H.U. Simon. On the number of examples and stages needed for learning decision trees. Technical Report SFB124-90-07, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1990. 15 pages.

• H. Wu. Pseudoexhaustive Test Generators. Technical Report SFB124-90-19, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1990.

• H.U. Simon. On relations between graph problems, mathematical programming and the geometry of numbers. Technical Report SFB124-89-03, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1989. 18 pages.

• B. Becker and U. Sparmann. Computations over finite monoids and their test comlexity. Technical Report SFB124-88-13, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1988.

• R. Hahn, R. Krieger, U. Sparmann, and B. Becker. Strukturbasierte Selbsttests für arithmetische Schaltkreise. Technical Report SFB124-88-06, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1988. 56 Seiten.

• J. Hartmann. Ein C-Test für einen schnellen Multiplizierer. Technical Report SFB124-88-02, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1988. 54 Seiten.

• H.U. Simon. The analysis of dynamic and hybrid channel assignment. Technical Report SFB124-88-10, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1988. 18 pages.

• H.U. Simon. Continuous reductions among combinatorial optimization problems. Technical Report SFB124-88-05, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1988. 19 pages.

• H.U. Simon. On approximate solutons for combinatorial problems. Technical Report SFB124-88-15, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1988. 24 pages.

• F.J. Schmitt. Eine Heuristik zum Berechnen rechtwinkliger Steiner-Bäume. Technical Report SFB124-87-09, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1987.

• B. Becker, G. Hotz, R. Kolla, P. Molitor, and H.G. Osthof. CADIC - A system for hierarchical design of integrated circuits. Technical Report SFB124-86-07, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1986.

• U. Sparmann. Entwurf und Test eines Schaltkreises für das Pattern-Matching. Technical Report SFB124-86-12, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1986. 230 Seiten.

• B. Becker, G. Hotz, R. Kolla, and P. Molitor. Ein Cad-System zum Entwurf Integrierter Schaltungen. Technical Report SFB124-84-16, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1984.

Fachbereich Informatik, Universität des Saarlandes

• Günter Hotz. A remark on nondecidabilities of initial value problems of ODEs. Technical report, Universität des Saarlandes, FR Informatik, Postfach 15 11 50, 66041 Saarbrücken, Germany, 2003. Technical Report. (PostScript, PDF, 7 pages, 118030 bytes)

• Günter Hotz and Tobias Gärtner. Approximation von Folgen durch berechenbare Folgen - Eine neue Variante der Chaitin-Kolmogorov-Komplexität. Technical Report FB14-2002-01, Fakultät für Mathematik und Informatik, 66041 Saarbrücken, Germany, March 2002. Technical Report. (PostScript, 92885 bytes)

• Günter Hotz. Darstellung von Schaltfunktionen unter Ausnutzung von Symmetrien boolescher Algebren. Technical Report FB14-1999-02, Universität des Saarlandes, FB 14 Informatik, Postfach 15 11 50, 66041 Saarbrücken, Germany, March 1999. Technical Report. (Gzipped PostScript, 89 pages, 647460 bytes)

• Günter Hotz. A graph based parsing algorithm for context-free languages. Technical Report FB14-99-01, Universität des Saarlandes, FB 14 Informatik, Postfach 15 11 50, 66041 Saarbrücken, Germany, July 1999. Technical Report. (Gzipped PostScript, 6 pages, 46148 bytes)

  We present a simple algorithm deciding the word problem of c. f. languages in O(n^3). It decides this problem in time O(n^2) for unambiguous grammars and in time O(n) in the case of LR(k) grammars.

• Alexander Gamkrelidze and Thomas Burch. A parametrized sorting system for a large set of k-bit elements. Technical Report FB14-1998-01, Universität des Saarlandes, FB 14 Informatik, Postfach 15 11 50, 66041 Saarbrücken, Germany, December 1998. Technical Report. (Gzipped PostScript, 34 pages, 474496 bytes)

  We describe a parametrized sorting system for a large set of k-bit elements. The structure of the system is independent from the problem size and the type of the sorting set, as well as from the ordering relation defined on the set of the elements.

• Alexander Gamkrelidze, Günter Hotz, and Bin Zhu. Designing correct recursive circuits using semantics-preserving transformations of nets. Technical Report FB14-1998-02, Universität des Saarlandes, FB 14 Informatik, Postfach 15 11 50, 66041 Saarbrücken, Germany, December 1998. Technical Report. (Gzipped PostScript, 1 pages, 24557 bytes)

• Günter Hotz. Algorithmische Informationstheorie (Teil 1). Technical Report FB14-97-01, Universität des Saarlandes, FB 14 Informatik, Postfach 15 11 50, 66041 Saarbrücken, Germany, January 1997. Vorlesung an der Universität des Saarlandes, Wintersemester 1996/97. (Gzipped PostScript, 116 pages, 272435 bytes)

• Thomas Chadzelek, Günter Hotz, and Elmar Schömer. Heuristic motion planning with many degrees of freedom. Technical Report FB14-95-08, Universität des Saarlandes, FB 14 Informatik, Postfach 15 11 50, 66041 Saarbrücken, Germany, August 1995. (Gzipped PostScript, 48 pages, 306965 bytes)

  We present a general heuristic approach to the geometric motion planning problem with the aim to quickly solve intuitively simple problems. It is based on a divide-and-conquer path search strategy which makes inquiries about feasible paths; to answer these, we develop an efficient collision detection scheme that handles translations and rotations of polyhedra to compute all times of collision. The whole algorithm can be easily implemented and universally applied and has been successfully tested in a program for assembly planning.

• G. Hotz J. Eckstein and E. Schömer. Heuristische Bewegungsplanungsstrategien im IR^3. Technical Report FB14-95-05, Universität des Saarlandes, Saarbrücken, 1995. (Gzipped PostScript, 132 pages, 1368395 bytes)

  Two general heuristic approaches to the geometric motion planning problem are considered. Both heuristics make use of efficient collision detection algorithms and combine motion planning with collision detection to speed up planning or to extend planning facilities. The first approach tries to speed up motion planning by ignoring all obstacles in the scene which do not contribute to the planned collision-free path. In order to obtain such a minimal scene the heuristic computes a collision-free path in a scene and checks the planned paths for collisions with ignored obstacles using standard collision detection algorithms. The heuristic thereby conserves qualitative features of the algorithms used like completeness, computation of most-secure, euclidian-shortest or time-optimal paths. It can be used with any kind of motion planning algorithms like classical ones, algorithms for dynamical environments or multiple moving objects. The advantages of the heuristic are shown for a complete algorithm handling 3-dimensional objects with two translational degrees of freedom using the configuration space approach of Lozano-Perez and Wesley. The second heuristic extends the facilities of algorithms for static environments by classifying the obstacles in the scene in fixed and movable obstacles forming a motion planning problem with many degrees of freedom. The complex problem is decomposed in a series of simple problems which can be solved efficiently by known algorithms and the solutions are combined to a solution for the whole problem. It is shown that together with a problem modification strategy the heuristic nearly always extends and never reduces the facilities of motion planning algorithms in static environments.

• Yonggang Guan, Günter Hotz, and Armin Reichert. Tree grammars with multilinear interpretation. Technischer Bericht FB14-92-01, Fachbereich Informatik, Universität des Saarlandes, 1992. (Gzipped PostScript, 57 pages, 135009 bytes)

  We consider context-free grammars on trees and multilinear interpretations of the generated tree languages. An equivalent class of string rewriting systems, the coupled-context-free grammars are introduced and investigated. A hierarchy of language classes between CFL and CSL is obtained. Stepping up the hierarchy increases generation power only slightly which is measured by the ability for ``counting'' and ``copying''. Our grammars and language classes could be of practical interest for linguistic applications, i.e. for defining syntax of natural languages since they belong to the class of ``mildly-context-sensitive languages'' and provide a generalization of the Tree Adjoining Languages (TAL).

Externe Technische Berichte

• Günter Hotz, Gero Vierke, and Börn Schieffer. Analytic machines. Technical Report TR95-025, Electronic Colloquium on Computational Complexity, 1995. (Gzipped PostScript, 23 pages, 75883 bytes)

  In this paper the R-machines defined by Blum, Shub and Smale are generalized by allowing infinite convergent computations. The description of real numbers is infinite. Therefore, considering arithmetic operations on real numbers should also imply infinite computations on analytic machines. We prove that R -computable functions are Q -analytic. We show that R-machines extended by finite sets of strong analytic operations are still Q -analytic. The halting problem of the analytic machines contains the stability problem of dynamic systems. It follows with well known methods that this problem is not analytical decidable. This is in a sense a stronger result as the numerical undecidable stability in the theory of Kolmogoroff, Arnold and Moser. Keywords: R -computability, stability, approximation

• P. Molitor and C. Scholl. Communication Based Multilevel Synthesis for Multi-O utput Boolean Functions. Informatik-Berichte 29, Humbold-University, 10099 Berlin, Germany, 1994. (Gzipped PostScript, 16 pages, 67266 bytes)

• U. Sparmann and S.M. Reddy. Universal delay test sets for logic networks. Technical Report 05/94, Dept. of ECE, University of Iowa, 1994. (Gzipped PostScript, 13 pages, 148424 bytes)

  It has been shown earlier that, if we restrict to unate gate network (UGN) realizations, there exist universal test sets for boolean functions. Such a test set only depends on the function f, and checks any UGN realization of f for all multiple stuck-at faults and all robustly testable stuck-open faults. In this paper we prove that these universal test sets are much more powerful than implied by the above results: They also constitute complete delay fault test sets for arbitrary UGN implementations of a given function. This is even true for UGN networks which are not testable with respect to the gate or path delay fault model. Our ability to prove the temporal correctness of such circuit realizations, comes from the fact that we do not argue the correctness of individual paths, but complete path systems.