From 0c46af64ba9de14df2a1b556dd39017eec3f0b63 Mon Sep 17 00:00:00 2001 From: Marc Cromme Date: Fri, 1 Feb 2008 09:46:10 +0000 Subject: [PATCH] added example OAI data --- examples/oai-pmh/data/debug-record.xml | 29 + examples/oai-pmh/data/debug-utf8-record.xml | 40 + examples/oai-pmh/data/oai-caltech.xml | 2643 +++++++++++++++++++++++++++ 3 files changed, 2712 insertions(+) create mode 100644 examples/oai-pmh/data/debug-record.xml create mode 100644 examples/oai-pmh/data/debug-utf8-record.xml create mode 100644 examples/oai-pmh/data/oai-caltech.xml diff --git a/examples/oai-pmh/data/debug-record.xml b/examples/oai-pmh/data/debug-record.xml new file mode 100644 index 0000000..bbdccd6 --- /dev/null +++ b/examples/oai-pmh/data/debug-record.xml @@ -0,0 +1,29 @@ + + +
+ oai:caltechcstr.library.caltech.edu:4 + 2003-12-12 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + A Language Processor and a Sample Language + Ayres, Ronald + All Records + This thesis explores shared data in list structures and ambiguity in language processing. Tolerance of ambiguity is necessary to support clear and modular expression. Data sharing is necessary to support ambiguity efficiently. Data sharing is useful also in compiled programs to save memory and time. Let us define some terms. A rewrite grammar is a set of replacement rules each of which specifies that a given phrase may be replaced by another given phrase. Each replacement rule expresses a local translation. A parser finds those sequences of replacements that bring a given text to a machine handleable form. Each such sequence represents a meaning or interpretation for the given text. Tolerance of ambiguity or multiple interpretations for a given text is necessary so that subsequent processing can place further constraints upon the input text. This thesis presents a parser which efficiently, handles general-rewrite grammars. To conserve computer time and memory, only essential differences among multiple interpretations are represented and processed. If several interpretations for a given text are valid, the parser yields a meaning which represents the ambiguity as, locally as possible. Even an exponential number of distinct meanings may be represented in a polynomial amount of memory. This thesis also presents a language processing system which supports semantic processing via independent rewrite grammars. Each grammar represents a distinct aspect of the language. A given sequence of grammars becomes a sequence of passes, or process steps. Each pass derives a meaning with respect to one grammar and uses that meaning to generate phrases which will be interpreted by the next pass. Although linguistic specification is usually done with context-free grammars, features of this parser which support general-rewrite grammars are essential for the integration of passes. Not only ambiguity, but also the locality of ambiguity is preserved from one pass to the next. It is necessary to preserve +locality of ambiguity in order to avoid explosive computation arising from useless action among independent sets of interpretations. I have implemented a general-purpose programming language called ICL with this system. The fact that ICL's datatypes are processed by a rewrite grammar makes it simple to implement both user-defined datatype coercions and functions known as polymorphic operators whose definitions depend on parameter datatypes. Datatype coercions and Polymorphic operators reduce the amount,of specification required in algorithms to such an extent that a user can often modify declarations and achieve optimizations and changes in concept without modifying his algorithmic specification. ICL includes a simple and safe policy about pointers so that the user can ignore their existence completely if he wishes. ICL automatically maximizes data sharing and minimizes copying by adopting a "copy on write" policy. This policy supports the illusion that each and every reference to a data structure generates a +complete copy of that data structure. This same technique is used in the language processor itself to facilitate data sharing among multiple interpretations in ambiguous cases. + California Institute of Technology + 1978-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1978.2276-tr-78 + application/postscript + http://caltechcstr.library.caltech.edu/4/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/4/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1978.2276-tr-78 + + + diff --git a/examples/oai-pmh/data/debug-utf8-record.xml b/examples/oai-pmh/data/debug-utf8-record.xml new file mode 100644 index 0000000..41be0ec --- /dev/null +++ b/examples/oai-pmh/data/debug-utf8-record.xml @@ -0,0 +1,40 @@ + + + 2005-12-20T08:40:20Z + http://caltechcstr.library.caltech.edu/perl/oai2 + + +
+ oai:zebra.debug:blåbærgrød<&!/> + 2006-11-12 + xx7374617475733D756E707562 + xx7375626A656374733D656E676E2D636D7074 +
+ + + Danske processeringsfejl med blåbærgrød + Index Data + + blåbærgrød og <&!/> blåbærkage +Ingredienser: +3 æg +3 dl sukker +3 dl mel +1 tsk bagepulver +½ tsk stødt kardemomme +½ tsk stødt ingefær +100 g smør +250 g blåbær +½ dl sukker +Pisk æg og sukker luftigt og rør mel, bagepulver og krydderier i. Smelt smørret og rør det i dejen, som fyldes i en smurt form. Drys med bær og sukker og bag kagen ved 180 grader i ca 30 minutter. Fremstillingstid - 40 minutter + + Index data ApS + 2006-11-12 + Test + NonPeerReviewed + http://www.indexdata.com/zebra/doc + + + + + \ No newline at end of file diff --git a/examples/oai-pmh/data/oai-caltech.xml b/examples/oai-pmh/data/oai-caltech.xml new file mode 100644 index 0000000..35b1d36 --- /dev/null +++ b/examples/oai-pmh/data/oai-caltech.xml @@ -0,0 +1,2643 @@ + + + 2005-12-20T08:40:20Z + http://caltechcstr.library.caltech.edu/perl/oai2 + + +
+ oai:caltechcstr.library.caltech.edu:4 + 2003-12-12 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + A Language Processor and a Sample Language + Ayres, Ronald + All Records + This thesis explores shared data in list structures and ambiguity in language processing. Tolerance of ambiguity is necessary to support clear and modular expression. Data sharing is necessary to support ambiguity efficiently. Data sharing is useful also in compiled programs to save memory and time. Let us define some terms. A rewrite grammar is a set of replacement rules each of which specifies that a given phrase may be replaced by another given phrase. Each replacement rule expresses a local translation. A parser finds those sequences of replacements that bring a given text to a machine handleable form. Each such sequence represents a meaning or interpretation for the given text. Tolerance of ambiguity or multiple interpretations for a given text is necessary so that subsequent processing can place further constraints upon the input text. This thesis presents a parser which efficiently, handles general-rewrite grammars. To conserve computer time and memory, only essential differences among multiple interpretations are represented and processed. If several interpretations for a given text are valid, the parser yields a meaning which represents the ambiguity as, locally as possible. Even an exponential number of distinct meanings may be represented in a polynomial amount of memory. This thesis also presents a language processing system which supports semantic processing via independent rewrite grammars. Each grammar represents a distinct aspect of the language. A given sequence of grammars becomes a sequence of passes, or process steps. Each pass derives a meaning with respect to one grammar and uses that meaning to generate phrases which will be interpreted by the next pass. Although linguistic specification is usually done with context-free grammars, features of this parser which support general-rewrite grammars are essential for the integration of passes. Not only ambiguity, but also the locality of ambiguity is preserved from one pass to the next. It is necessary to preserve +locality of ambiguity in order to avoid explosive computation arising from useless action among independent sets of interpretations. I have implemented a general-purpose programming language called ICL with this system. The fact that ICL's datatypes are processed by a rewrite grammar makes it simple to implement both user-defined datatype coercions and functions known as polymorphic operators whose definitions depend on parameter datatypes. Datatype coercions and Polymorphic operators reduce the amount,of specification required in algorithms to such an extent that a user can often modify declarations and achieve optimizations and changes in concept without modifying his algorithmic specification. ICL includes a simple and safe policy about pointers so that the user can ignore their existence completely if he wishes. ICL automatically maximizes data sharing and minimizes copying by adopting a "copy on write" policy. This policy supports the illusion that each and every reference to a data structure generates a +complete copy of that data structure. This same technique is used in the language processor itself to facilitate data sharing among multiple interpretations in ambiguous cases. + California Institute of Technology + 1978-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1978.2276-tr-78 + application/postscript + http://caltechcstr.library.caltech.edu/4/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/4/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1978.2276-tr-78 + + + + +
+ oai:caltechcstr.library.caltech.edu:5 + 2001-04-20 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Compiling Communicating Processes into Delay-Insensitive VLSI Circuits + Martin, Alain J. + All Records + No abstract available. + California Institute of Technology + 1986-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1986.5210-tr-86 + application/postscript + http://caltechcstr.library.caltech.edu/5/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/5/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1986.5210-tr-86 + + + + +
+ oai:caltechcstr.library.caltech.edu:6 + 2001-04-20 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Submicron Systems Architecture: Semiannual Technical Report + Seitz, Charles L. + Kajiya, James T. + Martin, Alain J. + McEliece, Robert J. + Rem, Martin + All Records + No abstract available. + California Institute of Technology + 1986-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1986.5220-tr-86 + application/postscript + http://caltechcstr.library.caltech.edu/6/00/5220.ps + http://resolver.caltech.edu/CaltechCSTR:1986.5220-tr-86 + + + + +
+ oai:caltechcstr.library.caltech.edu:7 + 2001-04-20 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + A Parallel Execution Model for Logic Programming + Li, Peyyun Peggy + All Records + The Sync Model, a parallel execution method for logic programming, is proposed. The +Sync Model is a multiple-solution data driven model that realizes AND-parallelism and +OR-parallelism in a logic program assuming a message-passing multiprocessor system. +AND parallelism is implemented by constructing a dynamic data flow graph of the literals in +the clause body with an ordering algorithm. OR parallelism is achieved by adding special +Synchronization signals to the stream of partial solutions and synchronizing the multiple +streams with a merge algorithm. The Sync Model is proved to be sound and complete. +Soundness means it only generates correct solutions and completeness means it +generates all the correct solutions. The soundness and completeness of the Sync Model +are implied by the correctness of the merge algorithm. A new class of interconnection +networks, the Sneptree, is also presented. The Sneptree is an augmented complete binary +tree which can simulate an unbounded complete binary tree optimally. Amongst different +connection patterns of the Sneptree, some are regular and extensible so as to be well +suited for VLSI implementation. A recursive method is presented to generate the +H-structure layout of one type of the Sneptree, called the Cyclic Sneptree. A message +routing algorithm between any two leaf nodes of the Cyclic Sneptree is also presented. +The routing algorithm, which is of O(n) complexity, gives a good approximation to the +shortest path. The Sneptree is an ideal architecture for the Sync model, in which a +dynamic process tree is constructed. With a simple mapping algorithm, the Sync Model can +be mapped onto the Sneptree with highly-balanced load and low overhead. + California Institute of Technology + 1986-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1986.5227-tr-86 + application/postscript + http://caltechcstr.library.caltech.edu/7/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/7/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1986.5227-tr-86 + + + + +
+ oai:caltechcstr.library.caltech.edu:8 + 2001-04-20 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + On the Performance of k-ary n-cube Interconnection Networks + Dally, William J. + All Records + The performance of k-ary n-cube interconnection networks is analyzed under the assumption of constant wire +bisection. It is shown that low-dimensional k-ary n-cube networks (e.g., tori) have lower latency and higher hot-spot +throughput than high-dimensional networks (e.g., binary n-cubes) with the same bisection width. + California Institute of Technology + 1986-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1986.5228-tr-86 + application/postscript + http://caltechcstr.library.caltech.edu/8/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/8/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1986.5228-tr-86 + + + + +
+ oai:caltechcstr.library.caltech.edu:9 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Switch-Level Model and Simulator for MOS Digital Systems + Bryant, Randal E. + All Records + The switch-level model describes the logical behavior of digital systems implemented in metal oxide semiconductor (MOS) technology. In this model a network consists of a set of nodes connected by transistor "switches" with each node having a state 0, 1, or X (for invalid or uninitialized), and each transistor having a state "open", "closed", or "indeterminate". Many characteristics of 140S circuits can be modeled accurately, including: ratioed, complementary, and precharged logic-, dynamic and static storage; (bidirectional) pass transistors; busses; charge sharing; and sneak pa ths. In this paper we present a formal development of the switch-level model starting from a description of circuit behavior in terms of switch graphs. Then we describe an algorithm for a logic simulator based on the switch-level model which computes the new state of the network by solving a set of equations in a simple, discrete algebra. This algorithm has been implemented in the simulator MOSSIM II and has been used to simulate circuits containing over 10,000 transistors. By developing a formal theory of MOS logic circuits, we have achieved a greater degree of generality and accuracy than is found in other logic simulators for MOS. + California Institute of Technology + 1983-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1983.5065-tr-83 + application/postscript + http://caltechcstr.library.caltech.edu/9/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/9/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1983.5065-tr-83 + + + + +
+ oai:caltechcstr.library.caltech.edu:10 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Submicron Systems Architecture: Semiannual Technical Report + Seitz, Charles L. + Kajiya, James T. + Martin, Alain J. + McEliece, Robert J. + Rem, Martin + Van Tilborg, Henk + All Records + No abstract available. + California Institute of Technology + 1985-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1985.5178-tr-85 + application/postscript + http://caltechcstr.library.caltech.edu/10/00/5178.ps + http://resolver.caltech.edu/CaltechCSTR:1985.5178-tr-85 + + + + +
+ oai:caltechcstr.library.caltech.edu:11 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Combining Computation with Geometry + Lien, Sheue-Ling-Chang + All Records + This thesis seeks to establish mathematical principles and to provide efficient solutions to various time consuming operations in computer-aided geometric design. It contains a discussion of three major topics: (1) design validation by means of object interference detection, (2) object reconstruction through the union, intersection, and subtraction of two polyhedra, and (3) calculation of basic engineering properties such as volume, center of mass, or moments of inertia. Two criteria are presented for solving the problems of point-polygon enclosure and point polyhedron enclosure in object interference detection. An algorithm for efficient point-polyhedron-enclosure detection is presented. Singularities encountered in point-polyhedron-enclosure detection are categorized and simple methods for for resolving them are also included. A new scheme for representing solid objects, called skeletal polyhedron representation, is proposed. Also included are algorithms for performing set operations on polyhedra (or polygons) represented in skeletal polyhedron representation, algorithms for performing edge-edge intersection and face-face intersection in a set operation, and a perturbation method which can be used to resolve singularities for an easy execution of edge--edge intersection and face-face interaction. A symbolic method for calculating basic engineering properties (such as volume, center of mass, moments of inertia, and similar integral properties of geometrically complex solids) is proposed. The same method is generalized for computing the integral properties of a set combined polyhedron and for computing the integral properties of an arbitrary polyhedron inc m-dimensional (Rm) space. + California Institute of Technology + 1984-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1985.5185-tr-85 + application/postscript + http://caltechcstr.library.caltech.edu/11/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/11/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1985.5185-tr-85 + + + + +
+ oai:caltechcstr.library.caltech.edu:12 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Submicron Systems Architecture: Semiannual Technical Report + Seitz, Charles L. + Kajiya, James T. + Martin, Alain J. + McEliece, Robert J. + Rem, Martin + All Records + No abstract available. + California Institute of Technology + 1985-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1985.5202-tr-85 + application/postscript + http://caltechcstr.library.caltech.edu/12/00/postscript.ps + http://resolver.caltech.edu/CaltechCSTR:1985.5202-tr-85 + + + + +
+ oai:caltechcstr.library.caltech.edu:13 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + anaLOG: A functional Simulator for VLSI Neural Systems + Lazzaro, John Paul + All Records + No abstract available. + California Institute of Technology + 1986-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1986.5229-tr-86 + application/postscript + http://caltechcstr.library.caltech.edu/13/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/13/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1986.5229-tr-86 + + + + +
+ oai:caltechcstr.library.caltech.edu:14 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Monte Carlo Methods for 2-D Compaction + Mosteller, R. C. + All Records + A new method of compaction for VLSI circuits is presented. Compaction is done simultaneously in two dimensions and uses a Monte Carlo simulation method often referred to as simulated annealing for optimization. A new curvilinear representation for VLSI circuits, specifically chosen to make the compaction efficient, is developed. Experiments with numerous cells are presented that demonstrate this method to be as good as, or better than the hand compaction previously applied to these cells. Hand compaction was the best previously known method of compaction. An experimental evaluation is presented of how the run time complexity grows as the number, N, of objects in the circuit increases. The results of this evaluation indicates that the run time growth is order O(N log(A))f(d) where f(d) is a function of the density, d, and A is the initial cell area. The function f(d) appears to have negligible or no dependence on N. A hierarchical composition approach is developed which takes advantage of the capability of the curvilinear representation and the 2- dimensional compaction technique. + California Institute of Technology + 1986-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1986.5230-tr-86 + application/postscript + http://caltechcstr.library.caltech.edu/14/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/14/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1986.5230-tr-86 + + + + +
+ oai:caltechcstr.library.caltech.edu:15 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Some Results on Kolmogorov-Chaitin Complexity + Schweizer, David Lawrence + All Records + No abstract available. + California Institute of Technology + 1986-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1986.5233-tr-86 + application/postscript + http://caltechcstr.library.caltech.edu/15/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/15/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1986.5233-tr-86 + + + + +
+ oai:caltechcstr.library.caltech.edu:16 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Submicron Systems Architecture: Semiannual Technical Report + Seitz, Charles L. + Kajiya, James T. + Martin, Alain J. + McEliece, Robert J. + Rem, Martin + All Records + No abstract available. + California Institute of Technology + 1986-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1986.5235-tr-86 + application/postscript + http://caltechcstr.library.caltech.edu/16/00/5235.ps + http://resolver.caltech.edu/CaltechCSTR:1986.5235-tr-86 + + + + +
+ oai:caltechcstr.library.caltech.edu:17 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + An Approach to Concurrent Semantics Using Complete Traces + Van Horn, Kevin S. + All Records + No abstract available. + California Institute of Technology + 1986-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1986.5236-tr-86 + application/postscript + http://caltechcstr.library.caltech.edu/17/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/17/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1986.5236-tr-86 + + + + +
+ oai:caltechcstr.library.caltech.edu:18 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Incorporating Time in the New World of Computing Systems + Poh, Hean Lee + All Records + The New World of Computing System, referred to as the New World system, is a total system for the structuring, manipulation and communication of information. Time is a ubiquitous aspect of most databases. The aim of this thesis is to study the problems associated with the implementation of time in the New World system. Time information is not only stored in New World, they can be retrieved and processed to answer various types of user queries. This is an additional feature as compared to most models of time implementation in databases where the relationships between time intervals are not dealt with. To start with, ways of representing time in the form of floating point number are devised and discussed. Then the conversion of time information from its various user accustomed forms to New World system internal form and back are explored. Finally, the ambiguities and complexities involved in finding the intersection, subtraction, union and extension of two different sequences of time intervals associated with an object in a database are studied and algorithms for resolving these are presented . An explanation on how the crunchers work with the addition of time information is also given. This includes discussing about how quantifiers such as at least 2, how many etc. are handled in the New World system. Case studies are also conducted to test out these routines. As conclusion, the remaining problems associated with time implementation not covered in this thesis work are discussed. + California Institute of Technology + 1986-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1986.5238-tr-87 + application/postscript + http://caltechcstr.library.caltech.edu/18/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/18/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1986.5238-tr-87 + + + + +
+ oai:caltechcstr.library.caltech.edu:19 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Cantor User Report: Version 2.0 + Athas, William C. + Seitz, Charles L. + All Records + No abstract available. + California Institute of Technology + 1987-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1987.5232-tr-86 + application/postscript + http://caltechcstr.library.caltech.edu/19/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/19/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1987.5232-tr-86 + + + + +
+ oai:caltechcstr.library.caltech.edu:20 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + A High Performance Implementation of Prolog + Newton, Michael O. + All Records + We discuss an efficient implementation of the Warren Abstract Machine (WAM) [12] in detail. Special attention is given to data formats, memory layout, WAM optimizations and code generation techniques. A final section describes some hardware considerations for even higher performance execution. Currently the compiler produces code that runs at approximately 900,000 logical inferences per second (LIPS) on a single processor of an IBM 3090 using the naive reverse benchmark. Using several of the yet unimplemented optimizations, we expect this figure to top one million LIPS. + California Institute of Technology + 1987-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1987.5234-tr-86 + application/postscript + http://caltechcstr.library.caltech.edu/20/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/20/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1987.5234-tr-86 + + + + +
+ oai:caltechcstr.library.caltech.edu:21 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Submicron Systems Architecture: Semiannual Technical Report + Seitz, Charles L. + Martin, Alain J. + McEliece, Robert J. + Rem, Martin + All Records + No abstract available. + California Institute of Technology + 1987-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1987.5240-tr-87 + application/postscript + http://caltechcstr.library.caltech.edu/21/00/5240.ps + http://resolver.caltech.edu/CaltechCSTR:1987.5240-tr-87 + + + + +
+ oai:caltechcstr.library.caltech.edu:22 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + VLSI Mesh Routing Systems + Flaig, Charles M. + All Records + No abstact available. + California Institute of Technology + 1987-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1987.5241-tr-87 + application/postscript + http://caltechcstr.library.caltech.edu/22/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/22/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1987.5241-tr-87 + + + + +
+ oai:caltechcstr.library.caltech.edu:23 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Fine Grain Concurrent Computations + Athas, William C. + All Records + This thesis develops a computational model, a programming notation, and a set of programming principles to further and to demonstrate the practicality of programming fine grain concurrent computers. Programs are expressed in the computational model as a collection of definitions of autonomous computing agents called objects. In the execution of a program, the objects communicate data and synchronize their actions exclusively by message-passing. An object executes its definition only in response to receiving a message, and its actions may include sending messages, creating new objects, and modifying its own internal state. The number of actions that occur in response to a message is finite; Turing computability is achieved not within a single object, but through the interaction of objects. A new concurrent programming notation Cantor is used to demonstrate the cognitive process of writing programs using the object model. Programs for numerical sieves, sorting, the eight queens problem, and Gaussian elimination are fully described. Each of these programs involve up to thousands of objects in their execution. The general programming strategy is to first partition objects by their overall behavior and then to program the behaviors to be self-organizing. The semantics of Cantor are made precise through the definition of a formal semantics for Cantor and the object model. Objects are modelled as finite automata. The formal semantics is useful for proving program properties and for building frameworks to capture specific properties of object programs. The mathematical frameworks are constructed for building object graphs independently of program execution and for systematically removing objects that are irrelevant to program execution (garbage collection). The formal semantics are complemented by experiments that allow one to study the dynamics of the execution of Cantor programs on fine grain concurrent computers. The clean semantics of Cantor suggests simple metrics for evaluating the execution of concurrent programs for an ideal, abstract implementation. Program performance is also evaluated for environments where computing resources are limited. Prom the results of these experiments, hardware and software architectures for organizing fine grain message-passing computations is proposed, including support for fault tolerance and for garbage collection. + + + California Institute of Technology + 1987-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1987.5242-tr-87 + application/postscript + http://caltechcstr.library.caltech.edu/23/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/23/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1987.5242-tr-87 + + + + +
+ oai:caltechcstr.library.caltech.edu:24 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Multicomputers + Athas, William C. + Seitz, Charles L. + All Records + This report outlines the history, current status, current developments, and plans for the message-passing concurrent computers, or multicomputers, developed in the Submicron Systems Architecture Project at Caltech. These systems include the Cosmic Cube and its commercial descendants, two second-generation cosmic cubes currently in development, and the Mosaic C, a fine grain multicomputer whose nodes are single VLSI chips. Section 1 introduces the physical architectures, with particular attention to the characteristics of the message-passing networks. Section 2 describes the programming environments for the first and second generation medium grain size "cubes." Section 3 describes a fine grain concurrent object-oriented programming notation called Cantor, which currently runs on cubes and sequential systems, and which will be used for application programming of the Mosaic C. + California Institute of Technology + 1987-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1987.5244-tr-87 + application/postscript + http://caltechcstr.library.caltech.edu/24/00/5244.ps + http://resolver.caltech.edu/CaltechCSTR:1987.5244-tr-87 + + + + +
+ oai:caltechcstr.library.caltech.edu:25 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + A Framework for Adaptive Routing + Ngai, John Y. + Seitz, Charles L. + All Records + No abstract available. + California Institute of Technology + 1987-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1987.5246-tr-87 + application/postscript + http://caltechcstr.library.caltech.edu/25/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/25/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1987.5246-tr-87 + + + + +
+ oai:caltechcstr.library.caltech.edu:26 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + VLSI Concurrent Computation for Music Synthesis + Wawrzynek, John + All Records + This thesis presents a very large-scale integrated circuit (VLSI) approach to the generation of musical sounds. The approach allows the generation of rich musical sounds using models that are easy to control and have parameters corresponding to many of the physical attributes of musical instruments. The generality of the approach for music synthesis is demonstrated by presenting several primitive sound generation mechanisms. Utilizing these primitives, several musical instruments are assembled to produce struck, plucked, and blown sounds. Refinements of the instruments are easily accomplished by adjusting or rearranging different functional components. A concurrent computing engine supporting the sound generation mechanisms is presented along with details of its VLSI implementation. Involved in the implementation is a new CMOS design methodology. Several alternative architectures for the computing engine are also presented and studied. + California Institute of Technology + 1987-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1987.5247-tr-87 + application/postscript + http://caltechcstr.library.caltech.edu/26/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/26/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1987.5247-tr-87 + + + + +
+ oai:caltechcstr.library.caltech.edu:27 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Logic from Programming Language Semantics + Choo, Young-il + All Records + Logic for reasoning about programs must proceed from the programming language semantics. It is our thesis that programs be considered as mathematical objects that can be reasoned about directly, rather than as linguistic expressions whose meanings are embedded in an intermediate formalism.Since the semantics of many programming language features (including recursion, type-free application, infinite structures, self-reference, and reflection) require models that are constructed as limits of partial objects, a logic for dealing with partial objects is required. Using the D infinity, model of the lambda-calculus, a logic (called continuous logic) for reasoning about partial objects is presented. In continuous logic, the logical operations (negation, implication, and quantification) are defined for each of the finite levels and then extended to the limit, giving us a model of type-free logic. The triples of Hoare Logic are interpreted as partial assertions over the domain of partial states, and contradictions arising from rules for function definitions are analyzed. Recursive procedures and recursive functions are both proved using mathematical induction. A domain of infinite lists is constructed as a model for languages with lazy evaluation and it is compared to an ordinal-heirarchic construction. A model of objects and multiple inheritance is constructed where objects are self-referential states and multiple inheritance is defined using the notion of product of classes. The reflective processor for a language with environment and continuation reflection is constructed as the projective limit of partial reflective processors of finite height. + California Institute of Technology + 1987-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1987.5249-tr-87 + application/octet-stream + http://caltechcstr.library.caltech.edu/27/00/1987.5249-tr-97.pdf + http://resolver.caltech.edu/CaltechCSTR:1987.5249-tr-87 + + + + +
+ oai:caltechcstr.library.caltech.edu:28 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Images, Numerical Analysis of Singularities and Shock Filters + Rudin, Leonid Iakov + All Records + This work is concerned primarily with establishing a natural mathematical framework for the Numerical Analysis of Singularities, a term which we coined for this new evolving branch of numerical analysis. The problem of analyzing singular behavior of nonsmooth functions is implicitly or explicitly ingrained in any successful attempt to extract information from images. The abundance of papers on the so called Edge Detection testifies to this statement. We attempt to make a fresh start by reformulating this old problem in the rigorous context of the Theory of Generalized Functions of several variables with stress put on the computational aspects of essential singularities. We state and prove a variant of the Divergence Theorem for discontinuous functions which we call Fundamental Theorem of Edge Detection, for it is the backbone of the advocated here numerical analysis based on the estimates of contribution5 furnished by the essential singularities of functions. We further extend this analysis to arbitrary order singularities by utilization of the Miranda's calculus of tangential derivatives. With this machinery we are able to explore computationally the internal geometry of singularities including singular, i.e., nonsmooth, singularity boundaries. This theory give5 rise to singularity detection scheme called "rotating thin masks" which is applicable to arbitrary order n-dimensional essential singularities. In the particular implementation we combined first-order detector with derived here various curvature detectors. Preliminary experimental results are presented. We also derive a new class of nonlinear singularity detection schemes based on tensor products of distributions. Finally, a novel computational approach to the problem of image enhancement is presented. We call this construction the Shock Filters, since it is founded on the nonlinear PDE's whose solutions exhibit formation of discontinuous profiles, corresponding to shock waves in gas dynamics. An algorithm for experimental Shock Filter, based on the upwind finite difference scheme is presented and tested on the one and two dimensional data. + California Institute of Technology + 1987-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1987.5250-tr-87 + application/pdf + http://caltechcstr.library.caltech.edu/28/01/00000028.pdf + http://resolver.caltech.edu/CaltechCSTR:1987.5250-tr-87 + + + + +
+ oai:caltechcstr.library.caltech.edu:29 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Conditional Knowledge as a Basis for Distributed Simulation + Chandy, K. Mani + Misra, Jay + All Records + A goal of this paper is to explore different ways of implementing distributed simulations. Distributed simulation grew out of sequential simulation, and it is possible that the way we think about distributed simulation is unduly influenced by its sequential origins. To free ourselves from unnecessary restrictions on the way we design distributed simulations, in this paper we define the distributed simulation problem somewhat differently than in the literature. We propose the concepts of "knowledge" and "conditional knowledge", to help us obtain a general framework to reason about distributed simulations without too close a coupling with any specific implementation method. The framework appears helpful in designing new ways of distributed simulations. Empirical studies of distributed simulations report widely varying results: some studies report improvements in speed that are almost linearly proportional to the number of computers in the system, while other studies report that distributed simulation is even slower than sequential simulation. The framework proposed in this paper seems to help in explaining the wide differences observed in empirical studies. Using our framework, we attempt to suggest properties that efficient "general-purpose" distributed discrete-event simulations must have. The paper assumes little prior knowledge of the literature on simuIation or distributed systems. We hope that the paper will serve as a tutorial in addition to providing additional insight. + California Institute of Technology + 1987-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1987.5251-tr-87 + application/postscript + http://caltechcstr.library.caltech.edu/29/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/29/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1987.5251-tr-87 + + + + +
+ oai:caltechcstr.library.caltech.edu:30 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Synthesis of Self-Timed Circuits by Program Transformation + Burns, Steven M. + Martin, Alain J. + All Records + No abstract available. + California Institute of Technology + 1987-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1987.5253-tr-87 + application/postscript + http://caltechcstr.library.caltech.edu/30/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/30/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1987.5253-tr-87 + + + + +
+ oai:caltechcstr.library.caltech.edu:31 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + A Synthesis Method for Self-Timed VLSI Circuits + Martin, Alain J. + All Records + No abstract available. + California Institute of Technology + 1987-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1987.5256-tr-87 + application/postscript + http://caltechcstr.library.caltech.edu/31/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/31/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1987.5256-tr-87 + + + + +
+ oai:caltechcstr.library.caltech.edu:32 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Submicron Systems Architecture Project:Semiannual Technical Report + Seitz, Charles L. + All Records + No abstract available. + California Institute of Technology + 1987-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1987.5258-tr-87 + application/postscript + http://caltechcstr.library.caltech.edu/32/00/5258.ps + http://resolver.caltech.edu/CaltechCSTR:1987.5258-tr-87 + + + + +
+ oai:caltechcstr.library.caltech.edu:33 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + PS: Polygon Streams: A Distributed Architecture for Incremental Computation Applied to Graphics + Gupta, Rajiv + All Records + Polygon Streams is a distributed system with multiple processors and strictly local communication. A unique custom VLSI chip that constitutes an independent processing module forms a stage of the PS pipeline. The number of these modules in PS is a variable that is determined by the application. PS features a modular architecture, multi-ported on-chip memory, bit-serial arithmetic, and a pipeline whose computation can be dynamically configured. The PS design closely subscribes to the system characteristics favored by VLSI. The task of scan conversion is very intensive in computation and pixel information access for rendering computer graphics images on raster scan displays. It is very coherent and suitable, however, for forward difference algorithms. The discrete and regular layout of the raster display in conjunction with the largely local effect of a pixel on an image, make rendering amenable to parallel architectures with localized memory and communication. These are precisely the attributes favored by VLSI and typical of PS. A modification of the Digital Differential Analyzer is implemented to Gouraud Shade and depth buffer convex polygons at high speeds. The scan conversion task is distributed over the processors to efficiently subdivide the image space and maximize concurrency of processor operation. A study of the tradeoffs and architectural choices of the PS reveal the merits and deficits of the PS approach in comparison with Pixel-Planes, Super-Buffers, and SLAMS. + California Institute of Technology + 1987-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1987.cs-tr-88-03 + application/postscript + http://caltechcstr.library.caltech.edu/33/00/88-03a.ps + http://resolver.caltech.edu/CaltechCSTR:1987.cs-tr-88-03 + + + + +
+ oai:caltechcstr.library.caltech.edu:35 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Automated Compilation of Concurrent Programs into Self-Timed Circuits + Burns, Steven M. + All Records + No abstract available. + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-02 + application/postscript + http://caltechcstr.library.caltech.edu/35/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/35/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-02 + + + + +
+ oai:caltechcstr.library.caltech.edu:36 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Cochlear Hydrodynamics Demystified + Lyon, Richard F. + Mead, Carver A. + All Records + Wave propagation in the mammalian cochlea (inner ear) is modeled as a unidirectional cascade of simple filters. The transfer functions of the low-order filter stages are completely determined by the wave-number vs. frequency solutions to the dispersion relations that describe the cochlea, which are in turn derived from twodimensional approximations to the fluid mechanics. Active undamping effects of the outer hair cells are easily included in the analysis and modeling, so that the results can be directly applied in the design of active adaptive cochlear models. + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-04 + application/postscript + http://caltechcstr.library.caltech.edu/36/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/36/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-04 + + + + +
+ oai:caltechcstr.library.caltech.edu:37 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Submicron Systems Architecture Project: Semiannual Technical Report + Seitz, Charles L. + All Records + No abstract available. + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-05 + application/postscript + http://caltechcstr.library.caltech.edu/37/00/88-05.ps + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-05 + + + + +
+ oai:caltechcstr.library.caltech.edu:38 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Theorems on Computations of Distributed Systems + Chandy, K. Mani + All Records + This paper presents theorems that are helpful in developing algorithms for the detection of stable properties, recording global snapshots and tracing the execution of distributed systems. The theorems are based on a property of channels. + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-06 + application/postscript + http://caltechcstr.library.caltech.edu/38/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/38/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-06 + + + + +
+ oai:caltechcstr.library.caltech.edu:39 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + The Hexagonal Resistive Network and the Circular Approximation + Feinstein, David I. + All Records + No abstract available. + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-07 + application/postscript + http://caltechcstr.library.caltech.edu/39/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/39/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-07 + + + + +
+ oai:caltechcstr.library.caltech.edu:40 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Pronouns + Roach, Kelly + All Records + No abstract available. This technical report was submitted in 1980 in partial fulfillment of the requirements for the degree of Master of Science. + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-09 + application/postscript + http://caltechcstr.library.caltech.edu/40/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/40/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-09 + + + + +
+ oai:caltechcstr.library.caltech.edu:41 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + The Reactive Kernel + Seizovic, Jakov N. + All Records + No abstract available. + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-10 + application/postscript + http://caltechcstr.library.caltech.edu/41/00/postscript.ps + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-10 + + + + +
+ oai:caltechcstr.library.caltech.edu:42 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + A Study of Fine-Grain Programming Using Cantor + Boden, Nanette J. + All Records + No abstract available. + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-11 + application/postscript + http://caltechcstr.library.caltech.edu/42/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/42/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-11 + + + + +
+ oai:caltechcstr.library.caltech.edu:43 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + A Comparison of Strict and Non-Strict Semantics for Lists + Burch, Jerry R. + All Records + No abstract available. + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-12 + application/postscript + http://caltechcstr.library.caltech.edu/43/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/43/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-12 + + + + +
+ oai:caltechcstr.library.caltech.edu:44 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + A Message-Passing Model for Highly Concurrent Computation + Martin, Alain J. + All Records + No abstract available. + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-13 + application/postscript + http://caltechcstr.library.caltech.edu/44/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/44/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-13 + + + + +
+ oai:caltechcstr.library.caltech.edu:45 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Syntax-Directed Translation of Concurrent Programs into Self-Timed Circuits + Burns, Steven M. + Martin, Alain J. + All Records + No abstract available. + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-14 + application/postscript + http://caltechcstr.library.caltech.edu/45/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/45/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-14 + + + + +
+ oai:caltechcstr.library.caltech.edu:46 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Applications of Surface Networks to Sampling Problems in Computer Graphics + Von Herzen, Brian + All Records + This thesis develops the theory, algorithms and data structures for adaptive sampling of parametric functions, which can represent the shapes and motions of physical objects. For the first time, ensured methods are derived for determining collisions and other interactions for a broad class of parametric functions. A new data structure, called a surface network, is developed for the collision algorithm and for other sampling problems in computer graphics. A surface network organizes a set of parametric samples into a hierarchy. Surface networks are shown to be good for rendering images, for approximating surfaces, and for modeling physical environments. The basic notion of a surface network is generalized to higher-dimensional problems such as collision detection. We may think of a two-dimensional network covering a three-dimensional solid, or an n-dimensional network embedded in a higher-dimensional space. Surface networks are applied to the problems of adaptive sampling of static parametric surfaces, to adaptive sampling of time-dependent parametric surfaces, and to a variety of applications in computer graphics, robotics, and aviation. First we develop the theory for adaptive sampling of static surfaces. We explore bounding volumes that enclose static surfaces, subdivision mechanisms that adjust the sampling density, and subdivision criteria that determine where samples should be placed. A new method is developed for creating bounding ellipsoids of parametric surfaces using a Lipschitz condition to place bounds on the derivatives of parametric functions. The bounding volumes are arranged in a hierarchy based on the hierarchy of the surface network. The method ensures that the bounding volume hierarchy contains the parametric surface completely. The bounding volumes are useful for computing surface intersections. They are potentially useful for ray tracing of parametric surfaces. We develop and examine a variety of subdivision mechanisms to control the sampling process for parametric functions. Some of the methods are shown to improve the robustness of adaptive sampling. Algorithms for one mechanism, using bintrees of right parametric triangles, are particularly simple and robust. A set of empirical subdivision criteria determine where to sample a surface, when we have no additional information about the surface. Parametric samples are concentrated in regions of high curvature, and along intersection boundaries. Once the foundations of adaptive sampling for static surfaces are described, we examine time-dependent surfaces. Based on results with the empirical subdivision criteria for static surfaces, we derive ensured criteria for collision determination. We develop a new set of rectangular bounding volumes, apply a standard L-dimensional subdivision mechanism called k-d trees, and develop criteria for ensuring that we detect collisions between parametric surfaces. We produce rectangular bounding boxes using a "Jacobian''-style matrix of Lipschitz conditions on the parametric function. The rectangular method produces even tighter bounds on the surface than the ellipsoidal method, and is effective for computing collisions between parametric surfaces. A new collision determination technique is developed that can detect collisions of parametric functions, based on surface network hierarchies. The technique guarantees that the first collision is found, to within the temporal accuracy of the computation, for surfaces with bounded parametric derivatives. Alternatively, it is possible to guarantee that no collisions occur for the same class of surfaces. When a collision is found, the technique reports the location and parameters of the collision as well as the time of first collision. Finally, we examine several applications of the sampling methods. Surface networks are applied to the problem of converting a two-dimensional image, or texture map, into a set of triangles that tile the plane. Many polygon-rendering systems do not provide the capability of rendering surfaces with textures. The technique converts textures to triangles that can be rendered directly by a polygon system. In addition, potential applications of the collision determination techniques are discussed, including robotics and air-traffic control problems. + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-15 + application/postscript + http://caltechcstr.library.caltech.edu/46/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/46/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-15 + + + + +
+ oai:caltechcstr.library.caltech.edu:47 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Programming Parallel Computers + Chandy, K. Mani + All Records + This paper is from a keynote address to the IEEE International Conference on Computer Languages, October 9, 1988. Keynote addresses are expected to be provocative (and perhaps even entertaining), but not necessarily scholarly. The reader should be warned that this talk was prepared with these expectations in mind.Parallel computers offer the potential of great speed at low cost. The promise of parallelism is limited by the ability to program parallel machines effectively. This paper explores the opportunities and the problems of parallel computing. Technological and economic trends are studied with a view towards determining where the field of parallel computing is going. An approach to parallel programming, called UNITY, is described. UNITY was developed by Jay Misra and myself, and is described in [Chandy]. Extensions to UNITY are discussed; these extensions were motivated by discussions with Chuck Seitz + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-16 + application/postscript + http://caltechcstr.library.caltech.edu/47/00/88-16.ps + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-16 + + + + +
+ oai:caltechcstr.library.caltech.edu:48 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Constrained Differential Optimization for Neural Networks + Platt, John C. + Barr, Alan H. + All Records + Many optimization models of neural networks need constraints to restrict the space of outputs to subspace which satisfies external criteria. Optimizations using energy methods yield "forces" which act upon the state of the neural network. The penalty method, in which quadratic energy constraints are added to an existing optimization energy, has become popular recently, but is not guaranteed to satisfy the constraint conditions when there are other forces on the neural model or when there are multiple constraints. In this paper, we present the basic differential multiplier method (BDMM), which satisfies constraints exactly; we create forces which gradually apply the constraints over time, using "neurons" that estimate Lagrange multipliers. The basic differential multiplier method is a system of differential equations first proposed by [ARROW] as an economic model. These differential equations locally converge to a constrained minimum. Examples of applications of the differential method of multipliers include enforcing permutation codewords in the analog decoding problem and enforcing valid tours in the traveling salesman problem. + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-17 + application/postscript + http://caltechcstr.library.caltech.edu/48/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/48/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-17 + + + + +
+ oai:caltechcstr.library.caltech.edu:49 + 2001-04-24 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Controlling Rigid Bodies with Dynamic Constraints + Barzel, Ronen + All Records + We present a technique, "Dynamic Constraints," for controlling the positions and orientations of rigid bodies n computer graphics models. The technique addresses the issue of providing control over a physically-based model, in which the bodies' behavior is determined by simulation of Newton's Laws of Motion. The "Dynamic Constraints" technique allows the modeler to control the configuration of bodies in a model by specifying constraints which must be met and maintained, as the simulation unfolds. To meet the constraints, we introduce forces into the model; these "constraint forces" forces are applied to the bodies that are constrained. We use an inverse dynamics method to derive a linear "constraint-force equation," whose solution yields the values of the constraint forces. We continually solve the constraint-force equation during the simulation of a model, so that the bodies' behavior will be consistent with the constraints. This thesis is accompanied by a narrated 10 -minuted videotape, "Caltech Modeling Demos, 1987" that contains several animations demonstrating the "Dynamic Constraints" technique. This thesis additionally includes a glossary of terms relating to physically-based modeling and dynamic constraints. + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-19 + application/postscript + http://caltechcstr.library.caltech.edu/49/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/49/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-19 + + + + +
+ oai:caltechcstr.library.caltech.edu:50 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Neural Network Design and the Complexity of Learning + Judd, Stephen J. + All Records + We formalize a notion of learning that characterizes the training of feed-forward networks. In the field of learning theory, it stands as a new model specialized for the type of learning problems that arise in connectionist networks. The formulation is similar to Valiant's [Va184] in that we ask what can be feasibly learned from examples and stored in a particular data structure. One can view the data structure resulting from Valiant-type learning as a 'sentence' in a language described by grammatical syntax rules. Neither the words nor their interrelationships are known a priori. Our learned data structure is more particular than Valiant's in that it must be a particular 'sentence'. The position and relationships of each 'word' are fully specified in advance and the learning system need only discover what the missing words are. This corresponds to the problem of finding retrieval functions for each node in a given network. We prove this problem NP-complete and thus demonstrate that learning in networks has no efficient general solution. Corollaries to the main theorem demonstrate the NP-completeness of several sub-cases. While the intractability of the problem precludes its solution in all these cases, we sketch some alternative definitions of the problem in a search for tractable sub-cases. One broad class of subcases is formed by placing constraints on the network architecture; we study one type in particular. The focus of these constraints is on families of 'shallow' architectures which are defined to have bounded depth and unbounded width. We introduce a perspective on shallow networks, called the Support Cone Interaction (SCI) graph, which is helpful in distinguishing tractable from intractable subcases: When the SC1 graph has tree-width O (log n), learning can be accomplished in polynomial time; when its tree-width is n omega (1) we find the problem NP-complete even if the SC1 graph is a simple 2-dimensional planar grid. + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-20 + application/pdf + http://caltechcstr.library.caltech.edu/50/01/88-20.pdf + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-20 + + + + +
+ oai:caltechcstr.library.caltech.edu:51 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Winner-Take-All Networks of O(N) Complexity + Lazzaro, J. + Ryckebusch, S. + Mahowald, M. A. + Mead, C. A. + All Records + No abstract available. + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-21 + application/postscript + http://caltechcstr.library.caltech.edu/51/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/51/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-21 + + + + +
+ oai:caltechcstr.library.caltech.edu:52 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Variants of the Chandy-Misra-Bryant Distributed Discrete-Event Simulation Algorithm + Su, Wen-King + Seitz, Charles L. + All Records + No abstract available. + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-22 + application/postscript + http://caltechcstr.library.caltech.edu/52/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/52/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-88-22 + + + + +
+ oai:caltechcstr.library.caltech.edu:53 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Communication Behavior of Linear Arrays of Processes + Lee, Tak K. + All Records + This paper investigates the communication behavior of a linear array of processes, each process implementing the same program. For programs with cyclic communication patterns, simple criteria for determining whether they induce constant response time on the array are established. Also, an algorithm is developed for characterizing programs with more general communication patterns. + + + California Institute of Technology + 1988-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-89-13 + application/postscript + http://caltechcstr.library.caltech.edu/53/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/53/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1988.cs-tr-89-13 + + + + +
+ oai:caltechcstr.library.caltech.edu:54 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + The Design of an Asynchronous Microprocessor + Martin, Alain J. + All Records + No abstract available. + California Institute of Technology + 1989-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-02 + application/postscript + http://caltechcstr.library.caltech.edu/54/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/54/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-02 + + + + +
+ oai:caltechcstr.library.caltech.edu:55 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Feature-Oriented Image Enhancement with Shock Filters, 1 + Rudin, Leonid I. + Osher, Stanley + All Records + No abstract available. + California Institute of Technology + 1989-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-03 + application/postscript + http://caltechcstr.library.caltech.edu/55/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/55/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-03 + + + + +
+ oai:caltechcstr.library.caltech.edu:56 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Submicron Systems Architecture Project: Semiannual Technical Report + Seitz, Charles L. + All Records + No abstract available. + California Institute of Technology + 1989-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-04 + application/postscript + http://caltechcstr.library.caltech.edu/56/00/89.04.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/56/01/89.04.pdf + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-04 + + + + +
+ oai:caltechcstr.library.caltech.edu:57 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + The Essence of Distributed Snapshots + Chandy, K. Mani + All Records + No abstract available. + California Institute of Technology + 1989-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-05 + application/postscript + http://caltechcstr.library.caltech.edu/57/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/57/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-05 + + + + +
+ oai:caltechcstr.library.caltech.edu:58 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + The First Aysnchronous Microprocessor: The Test Results + Martin, Alain J. + Burns, Steven M. + Lee, T. K. + Borkovic, Drazen + Hazewindus, Pieter J. + All Records + No abstract available. + California Institute of Technology + 1989-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-06 + application/postscript + http://caltechcstr.library.caltech.edu/58/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/58/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-06 + + + + +
+ oai:caltechcstr.library.caltech.edu:59 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Constrained methods for Neural Networks and Computer Graphics + Platt, John + All Records + Both computer graphics and neural networks are related, in that they model natural phenomena. Physically-based models are used by computer graphics researchers to create realistic, natural animation, and neural models are used by neural network researchers to create new algorithms or new circuits. To exploit successfully these graphical and neural models, engineers want models that fulfill designer-specified goals. These goals are converted into mathematical constraints. This thesis presents constraint methods for computer graphics and neural networks. The mathematical constraint methods modify the differential equations that govern the neural or physically-based models. The constraints methods gradually enforce the constraints exactly. This thesis also describes applications of constrained models to real problems. The first half of this thesis discusses constrained neural networks. The desired models and goals are often converted into constrained optimization problems. These optimization problems are solved using first-orderdifferential equations. There are a series of constraint methods which are applicable to optimization using differential equations: the Penalty Method adds extra terms to the optimization function which penalize violations of constraints, the Differential Multiplier Method adds subsidiary differential equations which estimate Lagrange multipliers to fulfill the constraints gradually and exactly, Rate-Controlled Constraints compute extra terms for the differential equation that force the system to fulfill the constraints exponentially. The applications of constrained neural networks include the creation of constrained circuits, error-correcting codes, symmetric edge detection for computer vision, and heuristics for the traveling salesman problem. The second half of this thesis discusses constrained computer graphics models. In computer graphics, the desired models and goals become constrained mechanical systems, which are typically simulated with second-order differential equations. The Penalty Method adds springs to the mechanical system to penalize violations of the constraints. Rate-Controlled Constraints add forces and impulses to the mechanical system to fulfill the constraints with critically damped motion. Constrained computer graphics models can be used to make deformable physically-based models follow the directives of a animator. + California Institute of Technology + 1989-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-07 + application/postscript + http://caltechcstr.library.caltech.edu/59/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/59/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-07 + + + + +
+ oai:caltechcstr.library.caltech.edu:60 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + A Framework for Adaptive Routing in Multicomputer Networks + Ngai, John Y. + All Records + Message-passing concurrent computers, also known as multicomputers, such as the Caltech Cosmic Cube [47] and its commercial descendents, consist of many computing nodes that interact with each other by sending and receiving messages over communication channels between the nodes. The communication networks of the second-generation machines, such as the Symult Series 2010 and the Intel iPSC2 [2], employ an oblivious wormhole-routing technique that guarantees deadlock freedom. The network performance of this highly evolved oblivious technique has reached a limit of being capable of delivering, under random traffic, a stable maximum sustained throughput of ~~45 to 50% of the limit set by the network bisection bandwidth, while maintaining acceptable network latency. This thesis examines the possibility of performing adaptive routing as an approach to further improving upon the performance and reliability of these networks. In an adaptive multipath routing scheme, message trajectories are no longer deterministic, but are continuously perturbed by local message loading. Message packets will tend to follow their shortest-distance routes to destinations in normal traffic loading, but can be detoured to longer but less-loaded routes as local congestion occurs. A simple adaptive cut-through packet-switching framework is described, and a number of fundamental issues concerning the theoretical feasibility of the adaptive approach are studied. Freedom of communication deadlock is achieved by following a coherent channel protocol and by applying voluntary misrouting as needed. Packet deliveries are assured by resolving channel-access conflicts according to a priority assignment. Fairness of network access is assured either by sending round-trip packets or by having each node follow a local injection-synchronization protocol. The performance behavior of the proposed adaptive cut-through framework is studied with stochastic modeling and analysis, as well as through extensive simulation experiments for the 2D and 3D rectilinear networks. Theoretical bounds on various average network-performance metrics are derived for these rectilinear networks. These bounds provide a standard frame of reference for interpreting the performance results. In addition to the potential gain in network performance, the adaptive approach offers the potential for exploiting the inherent path redundancy found in richly connected networks in order to perform fault-tolerant routing. Two convexity-related notions are introduced to characterize the conditions under which our adaptive routing formulation is adequate to provide fault-tolerant routing, with minimal change in routing hardware, The effectiveness of these notions is studied through extensive simulations, The 2D octagonal-mesh network is suggested; this displays excellent fault-tolerant potential under the adaptive routing framework. Both performance and reliability behaviors of the octagonal mesh are studied in detail. A number of implementation issues are examined. Encoding schemes for packet headers that admit simple incremental updates while providing all necessary routing information in the first flit of a relatively narrow flit width are developed. A pipelined control structure that allows a packet to cut through an intermediate node with a minimum delay of two cycles is described. A distributed clocking scheme is developed that eliminates the problem of global clock-signal distribution. Under this clocking scheme, the adaptive routers can be tessellated to form a network of arbitrary size. + California Institute of Technology + 1989-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-09 + application/postscript + http://caltechcstr.library.caltech.edu/60/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/60/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-09 + + + + +
+ oai:caltechcstr.library.caltech.edu:61 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Silicon Models of Early Audition + Lazzaro, John + All Records + This dissertation describes silicon integrated circuits that model known and proposed physiological structures in the early auditory system. Specifically, it describes silicon models of auditory-nerve response, of auditory localization in the barn owl, and of pitch perception. The integrated circuits model the structure as well as the function of the physiology; all subcircuits in the chips have anatomical correlates. The chips, two of which contain over 100,000 transistors, compute all outputs in real time, using analog, continuous-time processing. In most respects, chip responses approximate physiological or psychophysical response of the modeled biological systems. The dissertation also describes a novel nonlinear-inhibition circuit, which is a key component of two of the silicon models. + California Institute of Technology + 1990-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-10 + application/postscript + http://caltechcstr.library.caltech.edu/61/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/61/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-10 + + + + +
+ oai:caltechcstr.library.caltech.edu:62 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Reactive-Process Programming and Distributed Discrete-Event Simulation + Su, Wen-King + All Records + The same forces that spurred the development of multicomputers - the demand for better performance and economy - are driving the evolution of multicomputers in the direction of more abundant and less expensive computing nodes - the direction of fine-grain multicomputers. This evolution in multicomputer architecture derives from advances in integrated circuit, packaging, and message-routing technologies, and carries far-reaching implications in programming and applications. This thesis pursues that trend with a balanced treatment of multicomputer programming and applications. First, a reactive- process programming system - Reactive-C - is investigated; then, a model application - discreteevent simulation - is developed; finally, a number of logic-circuit simulators written in the Reactive-C notation are evaluated. One difficulty in multicomputer applications is the inefficiency of many distributed algorithms compared to their sequential counterparts. When better formulations are developed, they often scale poorly with increasing numbers of nodes, and their beneficial effects eventually vanish when many nodes are used. However, rules for programming are quite different when nodes are plentiful and cheap: The primary concern is to utilize all of the concurrency available in an application, rather than to utilize all of the computing cycles available in a machine. We have shown in our research that it is possible to extract the maximum concurrency of a simulation subject, even one as difficult as a logic circuit, when one simulation element is assigned to each node. Despite the initial inefficiency of a straightforward algorithm, as the the number of nodes increases, the computation time decreases linearly until there are only a few elements in each node. We conclude by suggesting a, technique to further increase the available concurrency when there are many more nodes than simulation elements. + California Institute of Technology + 1989-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-11 + application/postscript + http://caltechcstr.library.caltech.edu/62/00/postscript.ps + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-11 + + + + +
+ oai:caltechcstr.library.caltech.edu:63 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Submicron Systems Architecture Project: Semiannual Technial Report + Seitz, Charles L. + All Records + No abstract available. + California Institute of Technology + 1989-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-12 + application/postscript + http://caltechcstr.library.caltech.edu/63/00/89.12.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/63/01/89.12.pdf + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-89-12 + + + + +
+ oai:caltechcstr.library.caltech.edu:64 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Distributed Sorting + Hofstee, H. Peter + Martin, Alain J. + Van de Snepscheutt, Jan L. A. + All Records + No abstract available. + California Institute of Technology + 1989-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-90-06 + application/postscript + http://caltechcstr.library.caltech.edu/64/00/postscript.ps + http://resolver.caltech.edu/CaltechCSTR:1989.cs-tr-90-06 + + + + +
+ oai:caltechcstr.library.caltech.edu:65 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Properties of the V-C Dimension + Fyfe, Andrew + All Records + No abstract available. + California Institute of Technology + 1989-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-01 + application/postscript + http://caltechcstr.library.caltech.edu/65/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/65/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-01 + + + + +
+ oai:caltechcstr.library.caltech.edu:66 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Limitations to Delay-Insensitivity in Asynchronous Circuits + Martin, Alain J. + All Records + No abstract available. + California Institute of Technology + 1990-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-02 + application/postscript + http://caltechcstr.library.caltech.edu/66/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/66/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-02 + + + + +
+ oai:caltechcstr.library.caltech.edu:67 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + The Program Composition Project + Chandy, K. Mani + Taylor, Stephen + Kesselman, Carl + Foster, Ian + All Records + No abstract available. + California Institute of Technology + 1990-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-03 + application/postscript + http://caltechcstr.library.caltech.edu/67/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/67/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-03 + + + + +
+ oai:caltechcstr.library.caltech.edu:68 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Submicron Systems Architecture: Semiannual Technical Report + Seitz, Charles L. + All Records + No abstract available. + California Institute of Technology + 1990-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-05 + application/postscript + http://caltechcstr.library.caltech.edu/68/00/90-05.ps + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-05 + + + + +
+ oai:caltechcstr.library.caltech.edu:69 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Compiler Optimization of Array Data Storage + Gupta, Rajiv + Kajiya, James + All Records + The literature has witnessed much work aimed at improving the efficiency of mernory systems. The motivation is obvious: the high cost of page faults in hierarchical stores. Most architectures, including vector processors, shared - and distributed - memory multiprocessors, and interleaved memories, similarly reward data locality and predictable patterns of access. Most current endeavors, however, prefix the storage organization of data operands and either manipulate loops in the code, tailor algorithms, or tune prefetching strategies and replacement policies. A methodology and an algorithm for automatically organizing the storage of array data for efficient access by the executing code are described. The simple techniques presented may be incorporated in a compiler and are complementary to the other optimizations in the literature. Furthermore, examples in Fortran 8X and Fortran 77 pseudo-code support the general applicability of the work to programming languages, both scalar as well as array. Notwithstanding the column-major storage constraints, a technique for optiimizing storage in Fortran 77 is outlined. The prudence of of a compiler-optimized approach over a user-optimized approach to data storage organization is discussed. + California Institute of Technology + 1990-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-07 + application/postscript + http://caltechcstr.library.caltech.edu/69/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/69/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-07 + + + + +
+ oai:caltechcstr.library.caltech.edu:70 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Asynchronous Circuits for Token-Ring Mutual Exclusion + Martin, Alain J. + All Records + No abstract available. + California Institute of Technology + 1990-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-09 + application/postscript + http://caltechcstr.library.caltech.edu/70/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/70/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-09 + + + + +
+ oai:caltechcstr.library.caltech.edu:71 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + A Primer for Program Composition Notation + Chandy, K. Mani + Taylor, Stephen + All Records + This primer describes a notation for program composition. Program composition is putting programs together to get larger ones. PCN (Program Composition Notation) is a programming language that allows programmers to compose programs so that composed programs execute efficiently on uniprocessors, distributed-memory multicomputers or shared-memory multiprocessors. (Revised December 12, 1990) + California Institute of Technology + 1990-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-10 + application/pdf + http://caltechcstr.library.caltech.edu/71/00/1990.cs.tr-90-10a.pdf + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-10 + + + + +
+ oai:caltechcstr.library.caltech.edu:72 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Characterizing NP and Measuring Instance Complexity + Judd, Stephen + All Records + A generic NP-complete graph problem is described. The calculation of certain predicate on the graph is shown to be both necessary and sufficient to solve the problem and hence the calculation must be embedded in every algorithm solving NP problems. This observation gives rise to a metric on the difficulty of solving an instance of the problem. There appears to be an interesting phase transition in this metric when the graphs are generated at random in a "2-dimensional" extension. The metric is sensitive to 2 parameters governing the way graphs are generated: p, the density of edges in the graph, and K, related to the number of points in the graph. The metric seems to be finite in part of the (p,K)-space and infinite in the rest. If true, this phenomenon would demonstrate that NP-complete problems are truly monolithic and can easily exhibit strong intrinsic coupling of their variables throughout the entire instance. + California Institute of Technology + 1990-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-11 + application/postscript + http://caltechcstr.library.caltech.edu/72/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/72/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-11 + + + + +
+ oai:caltechcstr.library.caltech.edu:73 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Performance Analysis and Optimization of Asynchronous Circuits Produced by Martin Synthesis + Burns, Steven M. + All Records + We present a method for analyzing the timing performance of asynchronous circuits, in particular, those derived by program transformation from concurrent programs using the synthesis approach developed by Martin. The analysis method produces a performance metric (related to the time needed to perform an operation) in terms of the primitive gate delays of the circuit. Because the gate delays are functions of transistor sizes, the performance metric can be optimized with respect to these sizes. For a large class of asynchronous circuits -- including those produced by the Martin synthesis -- these techniques produce the global optimum of the performance metric. A CAD tool has been implemented to perform this optimization. + California Institute of Technology + 1990-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-12 + application/postscript + http://caltechcstr.library.caltech.edu/73/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/73/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-12 + + + + +
+ oai:caltechcstr.library.caltech.edu:74 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Submicron Systems Architecture: Semiannual Technical Report + Seitz, Charles L. + All Records + No abstract available. + California Institute of Technology + 1990-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-14 + application/postscript + http://caltechcstr.library.caltech.edu/74/00/90-14.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/74/01/90-14.pdf + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-14 + + + + +
+ oai:caltechcstr.library.caltech.edu:75 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + A Unified Framework for Constraint-Based Modeling + Kalra, Devendra + All Records + Constraint-based modeling techniques are emerging as an effective computer graphics approach for modeling and designing objects and their behaviors. In this thesis, computer graphics constraint techniques are unified into a single conceptual framework. The central themes of the thesis are methods to partition an arbitrary constraint problem in different domains and at different levels, and to provide a language and computational environment for modeling with constraints. Using partitioning and composition schemes, complex simulations can be built hierarchically from simpler simulations by "plugging" together separate modules. Fundamental and basic structures are designed and implemented to provide an "Assembly Language" for simulation systems. These structures are put together through a collection of interfaces, much like multiple languages that use the same assembler on a computer. We use strategies called refinement and partitioning to integrate seemingly disparate constraint techniques. We present Temporal Sequencing as an approach to design complex time behaviors of simulation systems. Refinement is a top-down approach of transforming high level representations of a constraint modeling problem into representations that are closer to the basic solution mechanisms available in the constraint environment, such as numerical solution methods. Partitioning is the decomposition of one constraint problem into multiple simpler constraint problems that are then studied separately. Temporal Sequencing is a methodology to design the time behavior of a simulation system by composing time behaviors of the system over subintervals of time. Using the above partitioning schemes for the solution and specification of a general constraint problem, we create a unified constraint environment with the capability to both solve constraint problem instances and to create specialized constraint systems. New methods of constraint specification and solution can be added into the same constraint framework as new methods are developed. Based on the above approach, a modeling system called "Our Constraint Environment" (OCE) has been implemented. A programming language as an extension to C++ has been designed to provide an interface to OCE. The language provides the constructs for the partitioning schemes discussed above. Simulations created using OCE have shown the efficacy of our design approach. Constraint-based modeling techniques are emerging as an effective computer graphics approach for modeling and designing objects and their behaviors. In this thesis, computer graphics constraint techniques are unified into a single conceptual framework. The central themes of the thesis are methods to partition an arbitrary constraint problem in different domains and at different levels, and to provide a language and computational environment for modeling with constraints. Using partitioning and composition schemes, complex simulations can be built hierarchically from simpler simulations by "plugging" together separate modules. Fundamental and basic structures are designed and implemented to provide an "Assembly Language" for simulation systems. These structures are put together through a collection of interfaces, much like multiple languages that use the same assembler on a computer. We use strategies called refinement and partitioning to integrate seemingly disparate constraint techniques. We present Temporal Sequencing as an approach to design complex time behaviors of simulation systems. Refinement is a top-down approach of transforming high level representations of a constraint modeling problem into representations that are closer to the basic solution mechanisms available in the constraint environment, such as numerical solution methods. Partitioning is the decomposition of one constraint problem into multiple simpler constraint problems that are then studied separately. Temporal Sequencing is a methodology to design the time behavior of a simulation system by composing time behaviors of the system over subintervals of time. Using the above partitioning schemes for the solution and specification of a general constraint problem, we create a unified constraint environment with the capability to both solve constraint problem instances and to create specialized constraint systems. New methods of constraint specification and solution can be added into the same constraint framework as new methods are developed. Based on the above approach, a modeling system called "Our Constraint Environment" (OCE) has been implemented. A programming language as an extension to C++ has been designed to provide an interface to OCE. The language provides the constructs for the partitioning schemes discussed above. Simulations created using OCE have shown the efficacy of our design approach. + California Institute of Technology + 1990-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-15 + application/postscript + http://caltechcstr.library.caltech.edu/75/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/75/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-15 + + + + +
+ oai:caltechcstr.library.caltech.edu:76 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Parallel Program Design and Generalized Weakest Preconditions + Lukkien, Johan J. + All Records + No abstract available. + California Institute of Technology + 1990-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-16 + application/postscript + http://caltechcstr.library.caltech.edu/76/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/76/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-16 + + + + +
+ oai:caltechcstr.library.caltech.edu:77 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Testing Delay-Insensitive Circuits + Martin, Alain J. + Hazewindus, Pieter J. + All Records + We show that a single stuck-at fault in a non-redundant delay-insensitive circuit results in a transition either not taking place or firing prematurely, or both, during an execution of the circuit. A transition not taking place can be tested easily, as this always prevents a transition on a primary output from taking place. A premature firing can also be tested but the addition of testing points may be required to enforce the premature firing and to propagate the transition to a primary output. Hence all single stuck-at faults are testable. All test sequences can be generated from the high-level specification of the circuit. The circuits are hazard-free in normal operation and during the tests. + California Institute of Technology + 1990-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-17 + application/postscript + http://caltechcstr.library.caltech.edu/77/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/77/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-17 + + + + +
+ oai:caltechcstr.library.caltech.edu:78 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Performance Analysis and Optimization of Asynchronous Circuits + Burns, Steven M. + Martin, Alain J. + All Records + We present a method for analyzing the time performance of asynchronous circuits, in paxticulax, those derived by program transformation from concurrent programs using the synthesis approach developed by the second author. The analysis method produces a performance metric (related to the time needed to perform an operation) in terms of the primitive gate delays of the circuit. Such a metric provides a quantitative means by which to compare competing designs. Because the gate delays are functions of transistor sizes, the performance metric can be optimized with respect to these sizes. For a large class of asynchronous circuits-including those produced by using our synthesis method-these techniques produce the global optimum of the performance metric. A CAD tool has been implemented to perform this optimization. + California Institute of Technology + 1990-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-18 + application/postscript + http://caltechcstr.library.caltech.edu/78/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/78/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-18 + + + + +
+ oai:caltechcstr.library.caltech.edu:80 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Weakest Preconditions for Progress + Lukkien, Johan J. + Van de Snepscheut, Jan L. A. + All Records + Predicate transformers that map the postcondition and all intermediate conditions of a command to a precondition are introduced. They can be used to specify certain progress properties of sequential programs. + California Institute of Technology + 1991-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-90-13 + application/postscript + http://caltechcstr.library.caltech.edu/80/00/postscript.ps + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-90-13 + + + + +
+ oai:caltechcstr.library.caltech.edu:81 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Performance Analysis and Optimization of Asynchronous Circuits + Burns, Steven M. + All Records + Analytical techniques are developed to determine the performance of asynchronous digital circuits. These techniques can be used to guide the designer during the synthesis of such a circuit, leading to a high-performance, efficient implementation. Optimization techniques are also developed that further improve this implementation by determining the optimal sizes of the low-level devices (CMOS transistors) that compose the circuit. + California Institute of Technology + 1991-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-01 + application/postscript + http://caltechcstr.library.caltech.edu/81/00/postscript.ps + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-01 + + + + +
+ oai:caltechcstr.library.caltech.edu:82 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Submicron Systems Architecture: Semiannual Technical Report + Seitz, Charles L. + All Records + No abstract available. + California Institute of Technology + 1991-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-03 + application/postscript + http://caltechcstr.library.caltech.edu/82/00/96-012.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/82/01/96-012.pdf + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-03 + + + + +
+ oai:caltechcstr.library.caltech.edu:83 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + A Distributed Implementation of a Task Pool + Hofstee, Peter H. + Lukkien, Johan J. + Van de Snepscheut, Jan L. A. + All Records + No abstract available. + California Institute of Technology + 1991-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-05 + application/postscript + http://caltechcstr.library.caltech.edu/83/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/83/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-05 + + + + +
+ oai:caltechcstr.library.caltech.edu:84 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + The Sliding Window Protocol Revisited + Van de Snepscheut, Jan L. A. + All Records + We give a correctness proof of the sliding window protocol. Both safety and liveness properties are addressed. We show how faulty channels can be represented as nondeterministic programs. The correctness proof is given as a sequence of correctness-preserving transformations of a sequential program that satisfies the original specification, with the exception that it does not have any faulty channels. We work as long as possible with a sequential program, although the transformation steps are guided by the aim of going to a distributed program. The final transformation steps consist in distributing the actions of the sequential program over a number of processes. + California Institute of Technology + 1991-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-06 + application/postscript + http://caltechcstr.library.caltech.edu/84/00/postscript.ps + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-06 + + + + +
+ oai:caltechcstr.library.caltech.edu:85 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Inversion of a Recursive Tree Traversal + Van de Snepscheut, Jan L. A. + All Records + A recursive algorithm for generating the prefix and infix traversaCls of a binary tree is inverted to obtain an algorithm for constructing the tree from its traversals. + California Institute of Technology + 1991-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-07 + application/postscript + http://caltechcstr.library.caltech.edu/85/00/postscript.ps + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-07 + + + + +
+ oai:caltechcstr.library.caltech.edu:86 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Asynchronous Datapaths and the Design of an Asynchronous Adder + Martin, Alain J. + All Records + This paper presents a general method for designing delay insensitive datapath circuits. Its emphasis is on the formal derivation of a circuit from its specification. We discuss the properties required in a code that is used to transmit data asynchronously, and we introduce such a code. We introduce a general method (in the form of a theorem) for distributing the evaluation of a function over a number of concurrent cells. This method requires that the code be "distributive." We apply the method to the familiar example of a ripple-carry adder, and we give a CMOS implementation of the adder. + California Institute of Technology + 1991-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-08 + application/postscript + http://caltechcstr.library.caltech.edu/86/00/postscript.ps + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-08 + + + + +
+ oai:caltechcstr.library.caltech.edu:87 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Invariance Hints and the VC Dimension + Fyfe, William John Andrew + All Records + We are interested in having a neural network learn an unknown function f. If the function satisfies an invariant of some sort, such as f is an odd function, then we want to be able to take advantage of this information and not have the network deduce the invariant based on an example of f. The invariant might be defined in terms of an explicit transformation of the input space under which f is constant. In this case it is possible to build a network thatnecessarily satisfies the invariant. In general, we define the invariant in terms of a partition of +the input space such that if x, x' are in the same partition element then f (x) = f (x'). An example of the invariant would be a pair (x, x') taken from a single partition element. We can combine examples of the invariant with examples of the function in the learning process. The +goal is to substitute examples of the invariant for examples of the function; the extent to +which we can actually do this depends on the appropriate VC dimensions. Simulations +verify, at least in simple cases, that examples of the invariant do aid the learning process. + California Institute of Technology + 1992-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-20 + application/postscript + http://caltechcstr.library.caltech.edu/87/00/92-20.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/87/01/92-20.pdf + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-20 + + + + +
+ oai:caltechcstr.library.caltech.edu:88 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Combinatorial Design of Tolerant Communicaiton Structures, with Applications to Non-Blocking Switches + Schweizer, David Lawrence + All Records + This thesis is an investigation into structures and strategies for fault-tolerant communication. We assume the existence of some set of nodes -- people, telephones, processors -- with a need to pass messages -- telephone calls, signals on a wire, data packet-- amongstthemselves. In Part I, our goal is to create a structure, that is, a pattern of interconnection, in which a designated source node can broadcast a message to (and through) a group of recipient nodes. We seek a structure in which every node has tightly limited fanout, but which is nonetheless able to function reliably even when challenged with significant numbers of node failures. The structures are described only in terms of their connectivity, and we therefore use the language of graph theory. Part 11 is based on the observation that certain transformations of the graphs in Part I produce graphs that look like previously studied structures called nonblocking switches. We show that these transformations, when applied to other graphs, yield new, easier approaches to, and proofs of, some known theorems. Part III is an independent body of work describing some investigations into possible extensions of the theory of Kolmogorov-Chaitin complexity into the foundations of pattern recognition. We prove the existence of an information theoretic metric on strings in which the distance between two strings is a measure of the amount of specification required for a universal computer to interconvert the strings. We also prove two topological theorems about this metric. + California Institute of Technology + 1991-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-09 + application/postscript + http://caltechcstr.library.caltech.edu/88/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/88/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-09 + + + + +
+ oai:caltechcstr.library.caltech.edu:89 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Submicron Systems Architecture Project :Semiannual Technical Report + Seitz, Charles L. + All Records + No abstract available. + California Institute of Technology + 1991-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-10 + application/postscript + http://caltechcstr.library.caltech.edu/89/00/CS-TR-91-10.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/89/01/CS-TR-91-10.pdf + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-10 + + + + +
+ oai:caltechcstr.library.caltech.edu:90 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + An Object-Oriented Real-Time Simulation of Music Performance Using Interactive Control + Dyer, Lounette M. + All Records + This thesis addresses the problem of interactive control of real-time music performance by sound synthesizers. The approach to the problem is based on an analysis of a real world orchestra performance. The problem is decomposed into components that are one-to-one with the real world entities: a conductor, performers, instruments, a score, and parts. A detailed object-oriented design of each of the components is presented and the objects and their real world counterparts are compared. An abstract digital music representation is defined to represent the musical composition that is to be performed by the system. A realtime control mechanism is described that allows a human user to control various aspects of the performance in musically expressive ways. The model is implemented in a system called ZED, which has been shown to simulate some of the dynamic behavior of the live orchestra. Issues concerning the trade-off between runtime efficiency and runtime flexibility are addressed in detail, as well as how these issues affect real-time scheduling, Optimization techniques are presented that help insure timeliness. The object-oriented features of inheritance and encapsulation are shown to provide the system with extensibility and flexibility. Several other approaches to the problem are briefly outlined and ZED is compared with these approaches. + California Institute of Technology + 1991-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-11 + application/postscript + http://caltechcstr.library.caltech.edu/90/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/90/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-11 + + + + +
+ oai:caltechcstr.library.caltech.edu:91 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Analog VLSI Circuits for Sensorimotor Feedback + DeWeerth, Stephen P. + All Records + This thesis presents a design framework and circuit implementations for integrating sensory and motor processing onto very large-scale integrated (VLSI) chips. The designs consist of analog circuits that are composed of bipolar and subthreshold MOS transistors. The primary emphasis in this work is the transformation from the spatially-encoded representation found in sensory images to a scalar representation that is useful for controlling motor systems. The thesis begins with a discussion of the aggregation of sensory signals and the resulting extraction of high-level features from sensory images. An integrated circuit that computes the centroid of a visual image is presented. A theoretical analysis of the function of this circuit in stimulus localization and a detailed error analysis are also presented. Next, the control of motors using pulse trains is discussed. Pulse-generating circuits for use in bidirectional motor control and the implementation of traditional control schemes are presented. A method for analyzing the operation of these controllers is also discussed. Finally, a framework for the combination of sensory aggregation and pulse-encoded outputs is presented. The need for signal normalization and circuits to perform this task are discussed. Two complete sensorimotor feedback systems are presented. + California Institute of Technology + 1991-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-13 + application/postscript + http://caltechcstr.library.caltech.edu/91/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/91/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-91-13 + + + + +
+ oai:caltechcstr.library.caltech.edu:92 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Synthesis of Asynchronous VLSI Circuits + Martin, Alain J. + All Records + No abstract available. + California Institute of Technology + 1991-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-93-28 + application/postscript + http://caltechcstr.library.caltech.edu/92/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/92/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1991.cs-tr-93-28 + + + + +
+ oai:caltechcstr.library.caltech.edu:93 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + A Tutorial Introduction to Mosaic Pascal + Lukkien, Johan J. + Van de Snepscheut, Johan L. A. + All Records + No abstract available. + California Institute of Technology + 1992-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-91-02 + application/postscript + http://caltechcstr.library.caltech.edu/93/00/postscript.ps + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-91-02 + + + + +
+ oai:caltechcstr.library.caltech.edu:95 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + A LISP Programming Exercise + Van de Snepscheut, Jan L. A. + All Records + We present the derivation of a solution to a LISP programming exercise. The derivation is in three steps. First, an inefficient solution is given. Second, the quintessence of a more efficient solution is captured in a number of equalities. Third, an efficient solution is derived from the inefficient one by a number of transformation steps, each of which is justified by the equalities. + California Institute of Technology + 1992-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-91-04 + application/postscript + http://caltechcstr.library.caltech.edu/95/00/postscript.ps + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-91-04 + + + + +
+ oai:caltechcstr.library.caltech.edu:96 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Delay-Insensitive Multiply-Accumulate Unit + Nielsen, Christian D. + Martin, Alain J. + All Records + No abstract available. + California Institute of Technology + 1992-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-03 + application/postscript + http://caltechcstr.library.caltech.edu/96/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/96/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-03 + + + + +
+ oai:caltechcstr.library.caltech.edu:98 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + A Simple Simulator for Multicomputer Routing Networks + Pertel, Michael J. + All Records + This report describes a concise program for simulating multicomputer routing networks [1]. The simulator is written in less than 200 lines of C code, and a complete listing is provided. Despite being terse, the simulator is exact, fast, and requires little memory. + California Institute of Technology + 1992-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-04 + application/postscript + http://caltechcstr.library.caltech.edu/98/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/98/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-04 + + + + +
+ oai:caltechcstr.library.caltech.edu:99 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Mesh Distance Formulae + Pertel, Michael J. + All Records + A table of useful summation formulae are derived, together with a Mathematica package for producing them. The distance distribution in mesh routing networks is derived. The mean and variance of the distance distribution are computed. A program for computing the distance distribution of any mesh is presented. + California Institute of Technology + 1992-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-05 + application/postscript + http://caltechcstr.library.caltech.edu/99/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/99/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-05 + + + + +
+ oai:caltechcstr.library.caltech.edu:100 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Material Classification of Magnetic Resonance Volume Data + Laidlaw, David H. + All Records + A major unsolved problem in computer graphics is that of making high-quality models. Traditionally, models have consisted of interactively or algorithmically described collections of graphics primitives such as polygons. The process of constructing these models is painstaking and often misses features and behavior that we wish to model. Models extracted from volume data collected from real, physical objects have the potential to show features and behavior that are difficult to capture using these traditional modeling methods. We use vector-valued magnetic resonance volume data in this thesis. The process of extracting models from such data involves four main steps: collecting the sampled volume data; preprocessing it to reduce artifacts from the collection process; classifying materials within the data; and creating either a rigid geometric model that is static, or a flexible, dynamic model that can be simulated. In this thesis we focus on the the first three steps. We present guidelines and techniques for collecting and processing magnetic resonance data to meet the needs of the later steps. Our material classification and model extraction techniques work better when the data values for a given material are constant throughout the dataset, when data values for different materials are different, and when the dataset is free of aliasing artifacts and noise. We present a new material-classification method that operates on vector-valued volume data. The method produces a continuous probability function for each material over the volume of the dataset, and requires no expert interaction to teach it different material classes. It operates by fitting peaks in the histogram of a collected dataset using parameterized gaussian bumps, and by using Bayes' law to calculate material probabilities, with each gaussian bump representing one material. To illustrate the classification method, we apply it to real magnetic resonance data of a human head, a human hand, a banana, and a jade plant. From the classified data, we produce "computationally stained" slices that discriminate among materials better than do the original grey-scale versions. We also generate volume-rendered images of classified datasets clearly showing different anatomical features of various materials. Finally, we extract preliminary static and dynamic geometric models of different tissues. + + + California Institute of Technology + 1992-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-21 + application/postscript + http://caltechcstr.library.caltech.edu/100/00/92-21.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/100/01/92-21.pdf + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-21 + + + + +
+ oai:caltechcstr.library.caltech.edu:102 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + A Critique of Adaptive Routing + Pertel, Michael J. + All Records + This report refutes claims that adaptive routing performs better than dimension-order routing. Simulation results are presented that show dimension-order routing achieves both higher throughput and lower latency than adaptive routing. Specious claims for the advantages of adaptive routing are critiqued. + California Institute of Technology + 1992-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-06 + application/postscript + http://caltechcstr.library.caltech.edu/102/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/102/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-06 + + + + +
+ oai:caltechcstr.library.caltech.edu:103 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Affinity: A Concurrent Programming System for Multicomputers + Steele, Craig S. + All Records + Affinity is an experiment to explore a simple, convenient, and expressive programming model that provides adequate power for complex programming tasks while setting few constraints on potential concurrency. Although the programmer is required to formulate a computational problem explicitly into medium-sized pieces of data and code, most of the additional functions necessary for concurrent execution are implicit. The execution of the light-weight, reactive processes, called actions, implicitly induces atomicity and consistency of data modifications. The programmer accesses shared data structures in a shared-memory fashion, but without the need for explicit locking to manage the problems of concurrent access and mutual exclusion. Program control flow is distributed and implicit. The name given to the programming model, Affinity, has a definition, "causal connection or relationship," that is fitting to the way programs are structured and scheduled. Affinity consistency and coherence properties provide a tractable discipline for the dangerous power of a concurrent, shared-memory programming style. Existing programming complexity-management techniques such as object-oriented languages can be used in this multicomputer environment. Affinity programs can compute consistent and correct results despite staleness of data, and asynchrony and nondeterminism in execution of code. Program correctness is invariant under replication, or cloning, of actions. This aspect of the model yields a simple and robust mechanism for fault- tolerance. The practicality of the Affinity programming model has been demonstrated by an implementation on a second-generation multicomputer, the Ametek S/2010. The implementation is distributed, scalable, and relatively insensitive to network latency. Affinity has demonstrated reasonable efficiency and performance for computations with tens of processing nodes, hundreds of actions, and thousands of shared data structures. + California Institute of Technology + 1992-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-08 + application/postscript + http://caltechcstr.library.caltech.edu/103/00/92-08a.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/103/01/92-08a.pdf + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-08 + + + + +
+ oai:caltechcstr.library.caltech.edu:104 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Mutual Exclusion in a Token Ring in CC++ + Binau, Ulla + All Records + This report describes a first attempt at using UNITY to verify reactive Compositional C++ (CC++) programs. We propose a distributed solution to the mutual exclusion problem using partially synchronous communication channels. The solution is described as a CC++ program, from which a small set of "basic" properties is derived. Using UNITY, we proof mutual exclusion and progress of the solution based on the set of properties derived from the code. + + + California Institute of Technology + 1992-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-11 + application/postscript + http://caltechcstr.library.caltech.edu/104/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/104/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-11 + + + + +
+ oai:caltechcstr.library.caltech.edu:105 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Compositional C++: Compositional Parallel Programming + Chandy, K. Mani + Kesselman, Carl + All Records + A compositional parallel program is a program constructed by composing component programs in parallel, where the composed program inherits properties of its components. In this paper, we describe a small extension of C++ called Compositional C++ or CC++ which is an object-oriented notation that supports compositional parallel programming. CC++ integrates different paradigms of parallel programming: data-parallel, task-parallel and object-parallel paradigms; imperative and declarative programming; shared memory and messagebased programs. CC++ is designed to be transportable across a range of MIMD architectures. + California Institute of Technology + 1992-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-13 + application/postscript + http://caltechcstr.library.caltech.edu/105/00/postscript.ps + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-13 + + + + +
+ oai:caltechcstr.library.caltech.edu:106 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Testing Delay-Insensitive Circuits + Hazewindus, Pieter Johannes + All Records + A method is developed to test delay-insensitive circuits, using the single stuck-at fault model. These circuits are synthesized from a high-level specification. Since the circuits are hazard-free by construction, there is no test for hazards in the circuit. Most faults cause the circuit to halt during test, since they cause an acknowledgement not to occur when it should. There are stuck-at faults that do not cause the circuit to halt under any condition. These are stimulating faults; they cause a premature firing of a production rule. For such a stimulating fault to be testable, the premature firing has to be propagated to a primary output. If this is not guaranteed to occur, then one or more test points have to be added to the circuit. Any stuck-at fault is testable, with the possible addition of test points. For combinational delay-insensitive circuits, finding test vectors is reduced to the same problem as for synchronous combinational logic. For sequential circuits, the synthesis method is used to find a test for each fault efficiently, to find the location of the test points, and to find a test that detects all faults in a circuit. The number of test points needed to fully test the circuit is very low, and the size of the additional testing circuitry is small. A test derived with a simple transformation of the handshaking expansion yields high fault coverage. Adding tests for the remaining faults results in a small complete test for the circuit. + California Institute of Technology + 1992-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-14 + application/postscript + http://caltechcstr.library.caltech.edu/106/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/106/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-14 + + + + +
+ oai:caltechcstr.library.caltech.edu:107 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Constructing some Distributed Programs + Hofstee, H. Peter + All Records + No abstract available. + California Institute of Technology + 1992-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-16 + application/postscript + http://caltechcstr.library.caltech.edu/107/00/postscript.ps + application/octet-stream + http://caltechcstr.library.caltech.edu/107/01/postscript.pdf + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-16 + + + + +
+ oai:caltechcstr.library.caltech.edu:108 + 2001-04-25 + 7374617475733D756E707562 + 7375626A656374733D656E676E2D636D7074 +
+ + + Submicron Systems Architecture Project : Semiannual Technical Report + Seitz, Charles L. + Martin, Alain + Van de Snepscheut, Jan L. A. + All Records + No abstract. + California Institute of Technology + 1992-01-01 + Monograph + NonPeerReviewed + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-17 + application/octet-stream + http://caltechcstr.library.caltech.edu/108/01/cs-92-17fin.pdf + http://resolver.caltech.edu/CaltechCSTR:1992.cs-tr-92-17 + + + + archive/100/1704605/oai_dc + + -- 1.7.10.4