Theses & Reports

---

Instructions for submitting a technical report or thesis.

You can find technical reports published prior to 1990 archived here.

• Ph.D. Thesis 1988 Parallel algorithms for band SPD systems of linear equations Bar-On, Ilan Abstract | PDF

  Title: Parallel algorithms for band SPD systems of linear equations

  Candidate: Bar-On, Ilan

  Advisor(s): Widlund, Olof

  Abstract:

  In this thesis we consider parallel algorithms for solving band symmetric positive definite systems of linear equations where the number of equations is much larger than the band width. Such systems arise in many practical applications for the dynamic analysis of structures such as the design of dams, bridges, ships, supersonic jets etc. Sequential methods for solving these systems require intolerable turnaround times and hence the importance of fast parallel algorithms for solving them. Our main contribution in this thesis is the presentation of a new practical parallel algorithm. Our algorithm runs in O(m $\*$ log n) time using nm/log n processors where n is the number of equations and m the band width. Hence, the algorithm is efficient. For tridiagonal systems the algorithm runs in O(log n) time using n/log n processors. We also develop a theoretical faster algorithm that runs in O(log m log n) time using nm$\sp2$/(log m log n) processors. This algorithm is efficient and runs as fast as the best currently known theoretical method. In chapter one we introduce the basic principles of parallel computations. In chapter two we review the basic algebraic and numerical properties of matrix computations. Here, we present a new parallel efficient algorithm for adding n k-bits integers in O(log n + log k) time based on the Fibbonachi sequence. In chapter three we consider parallel methods for solving band triangular systems which arise from the L-U decomposition of A. We conclude that this method is not as efficient for parallel computers as for sequential ones. In chapter four, we give a new efficient parallel algorithm for inverting a s.p.d. matrix in O(log$\sp2$n) time. We then present our new parallel algorithm for solving band s.p.d. systems, analyse its complexity, and show its improvement over the odd-even reduction algorithm. We conclude by pointing to yet unresolved problems in this field.

• Ph.D. Thesis 1988 ZLISP--a portable parallel LISP environment Dimitrovsky, Isaac Aaron Abstract | PDF

  Title: ZLISP--a portable parallel LISP environment

  Candidate: Dimitrovsky, Isaac Aaron

  Advisor(s): Harrison, Malcolm C.

  Abstract:

  This thesis concerns ZLISP, a portable parallel LISP environment for shared memory MIMD supercomputers. ZLISP was created as a vehicle for experimenting with parallel symbolic computing on a variety of supercomputer designs. It is a small but reasonably powerful subset of COMMON LISP that includes arrays, strings, structures, most of COMMON LISP's control flow functions, and a native code compiler, among other features. A low-level, flexible set of parallel primitives is provided that can support a wide spectrum of parallel programming styles. ZLISP currently runs on the NYU Ultracomputer prototype. A version that simulates parallelism runs on VAX and SUN minicomputers. I begin this thesis by discussing ZLISP's design and implementation. I attempt to justify the more difficult design decisions made during the development of ZLISP. I also give some details on how the more unusual parts of ZLISP are implemented. The full ZLISP reference manual is included as an appendix. I then turn to some parallel algorithms of independent interest that were discovered during the development of ZLISP. Many of these algorithms use the faa (fetch-and-add) operation, a versatile low-level synchronization primitive that has been promoted by the NYU Ultracomputer group and incorporated in several other supercomputer designs. I first describe some of the parallel algorithms used to implement ZLISP. These include an algorithm for parallel garbage collection and an algorithm for efficiently using hash tables in a parallel garbage collected environment. Finally, I cover some parallel algorithms provided for use by ZLISP programmers. I define the group lock, a new synchronization primitive useful in writing asynchronous parallel algorithms, and give some examples of its use in such applications as parallel stacks, heaps, and databases. I also present an assortment of space efficient parallel data structures such as queues, multiqueues, and stacks.

• Ph.D. Thesis 1988 Reasoning about shape and kinematic function in mechanical devices Joskowicz, Leo Abstract | PDF

  Title: Reasoning about shape and kinematic function in mechanical devices

  Candidate: Joskowicz, Leo

  Advisor(s): Davis, Ernest

  Abstract:

  This thesis presents a general framework for reasoning about the relationship between the shape of a solid object and its kinematic function in a mechanical device. Such a framework is essential for numerous reasoning tasks concerning mechanical devices such as analysis, prediction of behavior, and design. We propose to use an intermediate representation that relates the geometry of objects to their kinematic function in a mechanism; this representation stems from the notion of configuration spaces, originally introduced for motion planning. We show that configuration spaces are an appropriate symbolic representation for reasoning about the kinematics mechanical devices because the regions of the mechanism's configuration space can be interpreted as representing all the qualitatively different possible motions its objects. Our theory supports both qualitative and causal reasoning. To describe kinematic behavior functionally, we begin by developing two functional languages: possible motions descriptions and causal descriptions. We then present a two-step analysis procedure that starts by deducing the behavior of all kinematic pairs and then composes these behaviors to obtain the overall behavior of the mechanism. For a subclass of mechanisms (fixed axes mechanisms), we show that a simplified version of the composition operation can be used to obtain the overall behavior, and we outline a constraint propagation, label inferencing algorithm to produce a region diagram. This diagram constitutes a total qualitative envisionment of the mechanism's reachable behaviors. Given a sequence of input motions and a region diagram, we indicate how to predict the behavior of the mechanism. In the second part of this thesis, we address the problem of designing the shape of physical objects defined by a set of functional requirements. In particular, we show how to design kinematic pairs from a description of their desired behavior. We provide a general heuristic algorithm for innovative shape design, and present a number of efficient algorithms for special design cases. We also show how to design kinematic pairs when a qualitative or incomplete description of the desired behavior is provided.

• Ph.D. Thesis 1988 Use of three-dimensional curves in computer vision Kishon, Eyal Abstract | PDF

  Title: Use of three-dimensional curves in computer vision

  Candidate: Kishon, Eyal

  Advisor(s): Schwartz, Jacob T.

  Abstract:

  The objective of this work is to study the use of 3-D curves in model based object recognition. We approach the two main problems of object recognition, i.e., model formation and matching in a unified way. We propose a framework in which 3-D curves will be used both to represent objects in a database of models, and then present algorithms that use these curves to perform efficient matching between an observed object and a previously prepared database of object models. The motivation for this work comes from the fact that 3-D curves can describe in a natural way the objects from which they were extracted. Moreover, the use of these curves in the matching process has proved to be highly accurate while at the same time very efficient. In this work we present algorithms to extract 3-D curves from a pair of range and intensity images, and then algorithms that classify and separate between the different types of curves. We will also present two efficient algorithms for matching 3-D curves.

• Ph.D. Thesis 1988 Simulation-based understanding of texts about equipment Ksiezyk, Tomasz Bartlomiej Abstract | PDF

  Title: Simulation-based understanding of texts about equipment

  Candidate: Ksiezyk, Tomasz Bartlomiej

  Advisor(s): Grishman, Ralph

  Abstract:

  This thesis presents a natural language understanding system, operating in the domain of equipment consisting of mechanical, hydraulic, and electrical elements. The task of the system is to analyze reports regarding the failure, diagnosis and repair of equipment. We argue that a general knowledge of equipment is not sufficient for a full understanding of such reports. As an alternative, we propose a system which relies on a detailed simulation model to support language understanding. We describe the structure of the model and emphasize features specifically required for language understanding. We show how this model can be used in analyzing and determining the referents for complex noun phrases describing equipment parts. We outline the data structures used for concepts which are mentioned in the text but which have no permanent representation in the model, and explain how they are created during the text analysis. Similarly, we discuss the data structures for representing the facts conveyed by the text, and provide algorithms for translating text expressing facts into their representations. We point out the importance of identifying the implicit temporal and causal relations in the text and show how the simulation capabilities of the model support this task. We present a dynamic graphical interface which gives the user insight into the way the input has been understood by the system. Finally, we indicate how our system may be extended to facilitate dynamic (i.e. during the analysis of text) extensions to its data base, and to assist the user in entering new equipment models. Most aspects of the discussed system were implemented on a Symbolics Lisp machine.

• Ph.D. Thesis 1988 Extensions to SETL to support problem specification and transformation of imperative programs Lewis, Henry Merriman Abstract | PDF

  Title: Extensions to SETL to support problem specification and transformation of imperative programs

  Candidate: Lewis, Henry Merriman

  Advisor(s): Dewar, Robert

  Abstract:

  Programming by transformation is a reliable and efficient way to develop algorithms. An ideal methodology begins with high-level specifications of the problem to be solved. Such dictions are by nature concise, easy to understand, and easy to verify. They are free from the details that determine the method by which the solution is found, yet promote transformations leading to derivation of solutions. The user of the transformation system applies refinements and modifications that transform the problem specifications into algorithm specifications, and so is able to derive programs that solve the original problem. We propose extensions to the set-theoretic programming language SETL to support problem specifications. The resulting language realizes the ideals of problem specifications. The resulting language realizes the ideals of problem specification, and further supports direct execution of the highest-level specifications as a search over a solution space. Its dictions are imperative at all levels of derivation, so as to provide consistency of style among all versions, from problems to programs. We show how dictions of the form find variables $\vert$ conditions serve to specify problems, and how transformation of the conditions promotes derivation of algorithms. We propose dictions that allow concise specification of problems that require minimization of a function, and a variant that allows specification of problems that are inherently non-rigorous, or whose solutions admit approximation or tolerance. We suggest transformations of expressions that lead to algorithms employing formal differentiation of expressions or dynamic programming. Through examples we show that the method of transformational programming constitutes a tool for the specification, derivation, and discovery of algorithms.

• Ph.D. Thesis 1988 Foundations of a logic of knowledge, action, and communication Morgenstern, Leora Abstract | PDF

  Title: Foundations of a logic of knowledge, action, and communication

  Candidate: Morgenstern, Leora

  Advisor(s): Davis, Ernest

  Abstract:

  Most Artificial Intelligence planners work on the assumption that they have complete knowledge of their problem domain and situation, so that planning an action consists of searching for an action sequence that achieves some desired goal. In actual planning situations, agents rarely know enough to map out a detailed plan of action when they start out. Instead, they initially draw up a sketchy plan and fill in details as they proceed. This thesis presents a formalism that is expressive enough to describe this flexible planning process. We address ourselves to two central issues: (1) How can an agent determine that he knows enough to do an action? (Knowledge Preconditions Problem) (2) If the agent does not know enough, how can he plan to get the action done? (Ignorant Agent Problem) We demonstrate that modal logic is too weak to serve as the basis for such a theory, and choose instead to work within a first order logic augmented with quotation. We then discuss the Knower Paradoxes that arise from such syntactic treatments of knowledge, and propose a solution to these paradoxes based on Kripke's solution to the Liar Paradox. Next, we present a theory of action and planning that is powerful enough to describe partial plans and joint-effort plans. We then explain what knowledge an agent must have in order to successfully perform an action and how an ignorant agent can construct and execute complex plans in order to overcome his ignorance. A central observation underlying our solution to the Ignorant Agent Problem is that ignorant agents tend to use communicative acts, such as asking for information, and delegating, to plan around their ignorance. During the final part of this thesis, we therefore develop a theory of communication as an integrated part of our theory of action and planning. We show that this theory of communication is more expressive than standard Austinian-type speech act theories. The thesis includes comparisons of our theory with other syntactic and modal theories such as Konolige's and Moore's. We demonstrate that our theory is powerful enough to solve classes of problems that these theories cannot handle.

• Ph.D. Thesis 1988 Taliere: An interactive system for data structuring SETL programs Straub, Robert Michael Abstract | PDF

  Title: Taliere: An interactive system for data structuring SETL programs

  Candidate: Straub, Robert Michael

  Advisor(s): Schonberg, Edmond

  Abstract:

  This thesis describes a system designed to aid SETL programmers in the selection of data structures for the representation of program variables. The system uses information from the SETL optimizer, and provided interactively by the programmer, to select from the set and map representations which are available to implement SETL objects. We begin by describing previous work on data structure selection for very high level languages, including the data structure selection performed by the SETL optimizer. We then present a general description of a system for data structure selection for SETL programs. We describe techniques used to obtain useful information from a source program. This includes obtaining symbolic estimates of the execution frequencies of individual program operation, and estimates of the sizes of program objects. The data structures considered by the system are then described. We present a detailed description of the data structure selection algorithm, along with optimizations and heuristics used to improve the execution efficiency of the data structuring system. We conclude with examples comparing choices made by the system with choices made by a competent programmer and speculate on the eventual success of semi-automatic structuring systems.

• Ph.D. Thesis 1988 Operating system data structures for shared memory MIMD machines with fetch-and-add Wilson, James M. Abstract | PDF

  Title: Operating system data structures for shared memory MIMD machines with fetch-and-add

  Candidate: Wilson, James M.

  Advisor(s): Gottlieb, Allan

  Abstract:

  Ideally, procedures and data structures on a shared-memory MIMD machine should be serialization-free and concurrently accessible to avoid (potential) performance-limiting bottlenecks. The fetch-and-add coordination primitive, in conjunction with combining interconnection networks, has been proposed as a means for achieving this goal. The first is essentially an indivisible add-to-memory and the second combines simultaneous requests to the same memory location. In this thesis we address serialization-free memory and process management for a shared-memory MIMD machine with fetch-and-add and a combining network. To meet this goal we adopt a self-service paradigm for the operating system that permits each processing element (PE) to service its own requests (thereby avoiding central server bottlenecks). The success of this approach depends upon the use of concurrently accessible data structures to hold data shared among the PEs. We begin by reviewing existing fetch-and-add based queue and multiqueue (a compressed queue) implementations that support concurrent queue insertion and deletion. We then extend these implementations to include a new operations (e.g., the removal of an interior queue item) and new data structure representations (e.g., linked lists). Parallel memory allocation algorithms, many based on the modified queue and multiqueue data structures, are then given. These algorithms include parallel analogs to a number of existing serial algorithms such as Knuth's boundary tag method and the binary buddy system. Next, we define a set of primitives that permit various task activities, such as creation and scheduling, to be done in parallel. Task-switching readers/writers and event primitives are given as well. In the readers/writers implementations, reader activity is fully parallel in the absence of writers. An important feature of both the readers/writers and event implementations is that tasks waiting for a resource can be resumed in parallel by multiple PEs. We then demonstrate how high-level parallel programming constructs (e.g., parallel loops) may be implemented via the task primitives and the queue and multiqueue data structures. Finally, we prove that one of the readers/writers implementations satisfies certain correctness criteria including freedom from deadlock and the mutual exclusion of readers and writers.