N89-29057# North Carolina Univ., Chapel Hill. Dept. of Computer WALKTHROUGH-EXPLORING VIRTUAL WORLDS Annual John M. Airey and F. P. Brooks 16 Feb. 1989 7 p A virtual world system is a computer graphics system allowing natural real time interaction with a 3-d model world. Walkthrough is a virtual world system for architectures and their clients to explore buildings before they are built, so as to iteratively refine their specifications. Much of our virtual world research at Chapel Hill has involved molecules or human anatomy. In neither of these applications does one know exactly how the virtual world should seem to the explorer. In Walkthrough, on the other hand, the researcher can easily tell how closely the virtual world matches the real in the ways that matter. Any virtual world research project must continually improve in four aspects. The videotape, part 2, shows the progress to date, and gives short previews of some of GRA the advances not yet integrated into the system. N89-29058# North Carolina Univ., Chapel Hill. Dept. of Computer Science. A HETEROGENEOUS MULTIPROCESSOR GRAPHICS SYSTEM Henry Fuchs, John Poulton, John Eyles, Trey Greer, Jack (Contract N00014-86-K-0680; NSF DCI-86-01152; DARPA Order 6090) (AD-A208089; TR89-005) Avail: NTIS HC A03/MF A01 CSCL 12/5 The architecture and initial algorithms are introduced for Pixel-planes 5, a heterogeneous multi-computer designed both for high speed polygon and sphere rendering (1M Phong-shaded triangles/second) and for supporting algorithm and application research in interactive 3D graphics. Techniques are described for volume rendering at multiple frames per second, font generation directly from conic, spline descriptions, and rapid calculation of radiosity form factors. The hardware consists of up to 32 math-oriented processors, up to 16 rendering units, and a conventional 1280 x 1024-pixel frame buffer, interconnected by a 5 gigabit ring network. Each rendering unit consists of a 128 x 128-pixel array of processors-with-memory with parallel quadratic expression evaluation. Implemented on fast custom CMOS chips, this array has 208 bits/pixel on-chip and is connected to a video RAM memory system that provides 4,096 bits of off-chip memory. Rendering units can be independently reassigned to any part of the screen or to non-screen-oriented computation. A messagepassing operating system encourages algorithms to mix and match capabilities of the massively parallel rendering units with those of the math-oriented processors. As of January 1989, both hardware and software are still under construction, with initial GRA system operation scheduled for summer 1989. Geoffrion's structured modeling provides a very promising framework for the development of future Model Management Systems (MMS). This thesis presents a prototype that converts a mathematical representation of simple LP models to Geoffrion's structured modeling representations. The general procedures presented could be extended to convert an LP model represented in any precisely defined mathematical language. This would allow the development of integrated modeling environments based upon the structured modeling framework which could accept input in a number of common LP language formats. GRA N89-29060# Naval Postgraduate School, Monterey, CA. SOFTWARE ENGINEERING WITH DATABASE MANAGEMENT SYSTEMS M.S. Thesis Labros G. Karatasios Mar. 1989 189 p (AD-A208167) Avail: NTIS HC A09/MF A01 CSCL 12/5 The purpose of this thesis is to communicate a general knowledge of software engineering principles that can be applied to the development of a software system. Fundamental software engineering concepts are first discussed and then applied to a personnel database management system which is featured throughout the thesis. The individual tools and techniques that are used in each phase of the system development are widely known in the computer science community and each has been employed successfully in certain situations. GRA N89-29061*# Institute for Computer Applications in Science and Engineering, Hampton, VA. PARALLEL LANGUAGE CONSTRUCTS FOR TENSOR Piyush Mehrotra (Purdue Univ., West Lafayette, IN.) and John Distributed memory architectures offer high levels of performance and flexibility, but have proven awkard to program. Current languages for nonshared memory architectures provide relatively low level programming environment, and are poorly suited to modular programming, and to the construction of libraries. A set of language primitives designed to allow the specification of parallel numerical algorithms at a higher level is described. Tensor product array computations are focused on along with a simple but important class of numerical algorithms. The problem of programming 1-D kernal routines is focused on first, such as parallel tridiagonal solvers, and then how such parallel kernels can be combined to form parallel tensor product algorithms is examined. Author N89-29062# Universiteit Twente, Enschede (Netherlands). Dept. of Computer Science. APL CONVERSION SOFTWARE [APL CONVERSIE H. G. Posthuma May 1988 30 p In DUTCH A01 The APL conversion software and changes implemented therein are presented. The functions of the conversion program are explained. The structure of the sequential access inventory ASCII is outlined. The different APL programs are presented. The changes made in the software (changes to workspace Write and changes to workspace Qreaddec) are explained. Advice concerning the different subjects is given. The most important computer programs ESA and some basic explanations are included. N89-29063# Office National d'Etudes et de Recherches GENERALIZED PROJECTED GRADIENT-TYPE ITERATIVE 144 P (AD-A208166) Avail: NTIS HC A07/MF A01 CSCL 12/4 Claude Aumasson and Philippe Landiech 1988 95 P FRENCH; ENGLISH summary (ONERA-NT-1988-9; ISSN-0078-3781; ETN-89-94860) Avail: NTIS HC A05/MF A01 The theoretical aspects of the method are described, including the calculations of the cost and constraint sensitivities to variations in the control laws and parameters, a choice of objectives in constraint adjustments at each iteration, and the termination of the corresponding optimum control laws and parameters variations. An example of trajectory optimization is given, for which the analytical solution is known. It is shown that the software that implements the method works correctly. ESA N89-29064# Laboratoire d'Automatique et d'Analyse des ON THE COMPOSITION OF INTERCONNECTED SYSTEMS BY In FRENCH; ENGLISH summary Sponsored by CONICIT, Brazil; CEFI and Centre International des Etudiants et Stagiaires (LAAS-89.096; ETN-89-94871) Avail: NTIS HC A08/MF A01 A decomposition method based on dynamic programming principles is presented. Due to embedding and parametrization procedures, the technique works by arranging interconnected subsystems into a sequence and applying the principle of optimality across subsystems in the same manner as it is applied across stages in classical dynamic programming. The optimal design of an electric distribution network (static case) and the optimal short-term operation of a multireservoir power system are studied. ESA N89-29066# Universiteit Twente, Enschede (Netherlands). AN ALGORITHM FOR SMOOTH INTERPOLATION TO P. R. Pfluger (Amsterdam Univ., Netherlands) and R. H. J. (Memo-748; ISSN-0169-2690; ETN-89-95116) Avail: NTIS HC A03/MF A01 An algorithm which determines a smooth piecewise polynomial interpolant to scattered data in the plane is presented. An appropriate triangulation is chosen and the interpolant is determined in the splinespace with a high degree of polynomial precision. Numerical experiments using the interpolant method are presented. Tests performed on cardinal interpolation show the almost local behavior of the interpolant method. Five tests on different triangulations are used and results include confirmation of third order convergence. ESA N89-29067# National Aerospace Lab., Amsterdam (Netherlands). TOOLS FOR THE DEVELOPMENT AND USAGE OF F. J. Heerema, W. Loeve, and J. J. P. vanHulzen 17 Mar. 1987 30 p Presented at the 1st International Conference on Industrial and Applied Mathematics, Paris, France, 29 Jun. - 3 Jul. 1987 (NLR-MP-87020-U; ETN-89-95411) Avail: NTIS HC A03/MF A01 An infrastructure for information processing, comprising hardware and software, is discussed. This infrastructure can be applied to support research and engineering activities of the industry. A computer, a terminal network, and a supercomputer for fast computations are developed. The network allows access from outside to software, information from experiments, and digital simulations. The kernel of the software infrastructure consists of an engineering data management system with 4th generation characteristics. A standardized command language system (COLAS) for user interaction, and a method base system (MEBAS), which supports the management, assemblage and use of software components, are created. The main components of the infrastructure are facilities for data management, method management, and user interfaces, all implemented on a computer and terminal network. ESA N89-29068# Universiteit Twente, Enschede (Netherlands). Dept. of Computer Science. A LOGIC QUERY LANGUAGE AND ITS ALGEBRAIC 32 p Maurice A. W. Houtsma, Hendricus J. A. vanKuijk, Jan Flokstra, A logic query language, called PRISMAlog, is introduced. The language is one of the interfaces of a multiprocessor, main-memory database machine, called PRISMA. It is a language with a purely declarative semantics; the meaning of a program is given by its least fixed-point. PRISMAlog allows recursive rules, and supports operations like negation, arithmetic, aggregates, and group-by. Optimization of PRISMAlog programs is completely algebraic, and focusses on the use of distributed database techniques to introduce parallelism. Optimization criterion is minimization of response time. Techniques used to optimize PRISMAlog programs and to produce parallel schedules are illustrated. ESA N89-29069# Universiteit Twente, Enschede (Netherlands). Dept. of Computer Science. A METHOD OF SOFTWARE DEVELOPMENT USING S. M. M. Joosten 15 Dec. 1988 34 p A software development method which aims to be both formal and practical is presented. The attention is focused on the problem solving part of software development found in the very early stages of design. A format specification is developed and prototypes are implemented. A functional programming approach is used, which allows prototypes to be built that are very close to specification. External aspects, including manageability and maintainability, are improved, which considerably enhance the overall quality of software. The method does not require the use of any specific design language. The design is formalized in logic and mathematics to make it accessible to designers who do not want to learn new formalisms. An example of software development is given in which a non-trivial problem is solved. The entire development route is followed, from the formal specification to an imperative realization. ESA A survey of the strategy behind and the facilities of a code optimization package for REDUCE are given. A straight forward use of an Optimizer is discussed and illustrated. Declaration facilities and different file-handling possibilities are discussed. Detailed discussion of the underlying algorithms is avoided and the capabilities of the package are surveyed in general terms. Examples of straightforward and more advanced usage are shown. Conclusions are summarized and indications of future work are given. ESA N89-29071# National Aeronautical Lab., Bangalore (India). PHOTOETCHED DOUBLE SPIRAL DEVICE The computer graphic generation of a master drawing of a double spiral design is described along with the mask fabrication and the fabrication of the end product, the free filament resistance element of a 200 micron Manganin (Cu, Ni, Mn) foil. A listing of a program for generation of concentric circles is also listed. N89-29072# Author Universiteit Twente, Enschede (Netherlands). Faculty of Applied Mathematics. A SURVEY OF SELF-CONSISTENCY PROPERTIES IN Theo S. H. Driessen Jan. 1989 39 p (Memo-763; ISSN-0169-2690; ETN-89-95058) Avail: NTIS HC A03/MF A01 The use of reduced games in the study of cooperative games is reviewed in characteristic function form. The axiomatic characterizations of the Shapley value, the prekernel, the prenucleolus and the core are reviewed by means of an investigation into a self-consistency property in terms of the reduced games. The reduced game property for solutions and the reduced game property for a class of games are considered. From the class of games, including proof of reduced game property for the class of convex games, conclusions are drawn concerning the solutions on the relevant class of games. The reduced game property is applied to a bankruptcy problem. Results and proofs are given. ESA N89-29073# Universiteit Twente, Enschede (Netherlands). Faculty of Applied Mathematics. METHODS OF COMBINATORIAL OPTIMIZATION AND THEIR RANGE OF APPLICABILITY [VERFAHREN DER KOMBINATORISCHEN OPTIMIERUNG UND IHRE GUELTIGKEITSBEREICH] W. Kern Feb. 1989 46 p In GERMAN; ENGLISH summary (Memo-766; ISSN-0169-2690; ETN-89-95061) Avail: NTIS HC A03/MF A01 The basic techniques and methods of combinatorial optimization are outlined, and their range of applicability are investigated (i.e. a characterization of general classes of problems allowing a successful application of the methods). The matroid theory is introduced, and matroids are treated in connection with a number of combinatorial problems. The simplest method of combinatorial optimization, the Greedy algorithm, is presented, and a class of linear optimization problems which can be solved by the Greedy strategy is characterized. The simplex algorithm for solving linear programs is described. Linear programming relaxation is presented as a basic strategy for solving integral (nonlinear programming complete) optimization problems. An heuristic method (simulated annealing) for solving nonlinear-programming-complete problems is outlined. ESA The problem in minimizing total purchase cost of tinned iron sheets, for a tin factory with a fixed production program, and the exploitation of the price structure by the formulation of a combinatorial optimization problem are described. A combinatorial programming model of the problem is formulated and solutions to this model are obtained by Lagrangean relaxation and subgradient techniques. The principles of these methods are described and a computer program, written in TURBO PASCAL, was executed on a microcomputer, to implement them for the specific problem. Extensions, modifications, and other possible applications of the model are formulated including reduction of computation time and the purchase of arbitrary goods from various sellers on the basis of value order discounts. Technical details on the solving of knapsack problems, and the transformation of infeasible solutions to feasible, are included. ESA N89-29075# Universiteit Twente, Enschede (Netherlands). LANGUAGE CONSTRUCTS AND A SEARCH PROCEDURE TO Language constructs to model combinatorial problems, intended as an integrated part of an existing modeling language, are introduced. To use these constructs, the problem is stated, and an algorithm defined to solve it, which allows the construction of more exact and efficient algorithms describing heuristics that are derived from the character of the problem and are expressed in terms of problem components. The underlying algorithm chosen for solving the combinatorial problems is basically a depth-first search procedure. The language constructs are used to specify and control the search procedure and in this way to narrow down the search space. A major advantage of the search model is the ease of model modification. The proposed language constructs allow for the separation of the model into problem description and algorithm directives. Recommendations for improvements to the constructs are given. ESA N89-29076# Universiteit Twente, Enschede (Netherlands). Faculty of Applied Mathematics. THREE DIMENSIONAL RECONSTRUCTION FROM SERIAL CROSS SECTIONS BY SET VALUED INTERPOLATION R. H. J. Gmelig Meyling Dec. 1988 33 p (Memo-754; ISSN-0169-2690; ETN-89-95120) Avail: NTIS HC A03/MF A01 The problems of three dimensional reconstruction are addressed, and a computer aided reconstruction algorithm, based on the concept of set valued interpolation as proposed by Levin (1986), is described. The method is completely automatic and requires no human intervention. A set valued and shape preserving interpolation scheme is shown to greatly facilitate the detection of the boundary surface and allow the accurate reconstruction of closed three dimensional objects of abitrary shape. The use of low degree piecewise polynomials (splines), which are flexible and highly efficient, to solve the associated univariate interpolation problems, is shown to significantly improve the computational properties of the method. The use of a parallel computer architecture is shown to eliminate the potential drawback of high computational costs. The method is proposed to have practical importance in the medical field. N89-29077# Technische Univ., Delft (Netherlands). K. Jainandunsing 1989 195 p ESA Algorithms for solving systems of linear equations with a maximum degree of parallelism and pipelining are presented. Partitioning strategies for the design of systolic arrays with the number of processor elements independent of the size of the problem are developed. The synthesis of a concrete systolic array N89-29078# Universiteit Twente, Enschede (Netherlands). Dept. of Computer Science. A STATIC LOAD DISTRIBUTION STRATEGY FOR E. G. Zondag Dec. 1988 20 p (Memo-INF-88-43; ISBN-90-365-0242-X; ETN-89-95064) Avail: NTIS HC A03/MF A01 In order to avoid costly process migration which might restrict realtime behaviour in the TUMULT multi-processor system, a search for a static load determination process to optimize system throughput was initiated. A load distribution strategy for static assignment of processes in a processor pool is presented under the assumption that processes cannot migrate. A resource allocation is attempled that (nearly) optimizes the execution progress of the set or processes. A simple and a more complex, cost function, which take into account execution related process and processor attributes are defined. Methods for the calculation of a proper assignment using these functions, including a simulated annealing algorithm, are described. The strategy relies on the behavior histories of processes and processors. Problems concerning the general applicability of this strategy, its reliance on behavior stability, and its simple approach to task or machine learning, are outlined as future topics for consideration. ESA N89-29079# Universiteit Twente, Enschede (Netherlands). Dept. of Computer Science. THE APPLICATION OF CONSTRAINTS IN QUERY Hendricus J. A. vanKuijk 1988 84 p A hierarchy of static constraints is demonstrated to be at the foundation of a framework unifying the solution to a number of existing and new problems encountered during the overall process of (semantic) query optimization in (distributed) database systems. Domain constraints, attribute constraints, and tuple constraints are applied to explicitly represent knowledge inherent to the application being modeled. The context of the theory presented is found in the knowledge-based approach to semantic query optimization in a distributed environment and the explicit representation of query optimization knowledge of various sources so that it can be manged (added, deleted, modified). Constraints are used, to represent and apply semantic knowledge (including the so-called if-then rules known from literature), to augment selection and join predicate formulas to arrive at more efficient schedules for these operations, to define and apply horizontal fragmentation knowledge in case of distributed database systems, and to estimate more accurately the parameters of profiles of the relations resulting from relational operations. Given the individual constraints on relations, a mechanism is provided to derive the constraints on the relations resulting from relational operations. Conclusions are considered, including the power of this approach by virtue of its flexibity, and related to passible future discussion. ESA first three extensions are shown to be handled more or less straight forwardly and necessary design decisions are illustrated for the user defined (recursive) algebraic data types. The large amount of extra work required for the higher order functions is shown to necessitate a change in the analysis technique. An acceptable level is achieved by the division of the analysis into two parts and ESA subsequent independent handling. 62 COMPUTER SYSTEMS Includes computer networks and special application computer systems. N89-29081# Colorado Univ., Boulder. Optoelectronic Computing AN OPTOELECTRONIC MULTI-Gb/s PACKET SWITCHING J. R. Sauer (Bell Telephone Labs., Inc., Murray Hill, NJ.) Feb. 1989 35 p Prepared in cooperation with Colorado State Univ., Fort Collins (Grant NSF CDR-86-22236) (PB89-184345; OCS-TR-89-06) Avail: NTIS HC A03/MF A01 CSCL 09B An optoelectronic network architecture is proposed that would provide multi-Gb/s data for electronic users at the network access points. Constructed with current technology, the network transports short packets through multiple switching nodes optically. It is based on three interlocking concepts that exploit the advantages of optics: a simple interconnection topology supporting high connectivity and concurrency, a lean self-routing flow-through protocol permitting an optical implementation, and large-scale optical packet time compression/decompression to/from the electronic format of the GRA users. N89-29082# Massachusetts Inst. of Tech., Cambridge. Dept. of Electrical Engineering and Computer Science. A RECONFIGURABLE ARITHMETIC PROCESSOR M.S. Thesis James Alexander Stua Fiske Apr. 1989 72 p Sponsored in cooperation with Fonds pour la Formation de Chercheurs et l'Aide a la Recherche, NSF, GE Corp., and IBM Corp. (Contracts N00014-88-K-0738; N00014-87-K-0825; N00014-85-K-0124) (AD-A208323; VLSI-Memo-89-521) Copyright Avail: NTIS HC A04/MF A01 CSCL 12/6 Achieving high rates of floating-point computation is one of the primary goals of many computer designs. Many high speed floating-point datapaths have been designed in order to address this problem. However, conventional designs often neglect the real problem in achieving high performance floating-point: providing the necessary 1/0 bandwidth to keep the high speed datapaths busy. The Reconfigurable Arithmetic Processor (RAP) is an arithmetic processing node for a message-passing, MIMD concurrent computer. Its datapath is designed to sustain high rates of floating-point operations, while requiring only a fraction of the I/O bandwidth required by a conventional floating-point datapath. The RAP incorporates on one chip eight 4-bit serial, 64 bit floating-point arithmetic units connected by a switching network. By sequencing the switch through different patterns, the RAP chip calculates complete arithmetic formulas. By chaining together its arithmetic units the RAP eliminates the I/O bandwidth associated with storing and retrieving intermediate results, and reduces the amount of off chip data transfer. This thesis describes and evaluates the RAP architecture. It presents two important aspects of the chip design: the control logic design, and the schematic level design of the RAP datapath. GRA N89-29084# Massachusetts Inst. of Tech., Cambridge. Lab. for Computer Science. CHAPTER ON DISTRIBUTED COMPUTING Leslie Lamport and Nancy Lynch Feb. 1989 71 p Rigorous analysis starts with a precise model of a distributed system; the most popular models, differing in how they represent interprocess communication, are message passing, shared variables, and synchronous communication. The properties satisfied by an algorithm must be precisely stated and carefully proved; the most successful approach is based on assertional reasoning. Algorithms for solving particular problems in a distributed system can then be designed and analyzed. Typical of the problems that were addressed are: concurrently accessing shared data, achieving consensus, analyzing network topology, obtaining consistent global GRA information, and controlling database transactions. N89-29085# Naval Ocean Systems Center, San Diego, CA. S. P. Murphy May 1989 14 p (AD-A210148; NOSC/TD-1538) Avail: NTIS HC A03/MF A01 CSCL 12/6 The Naval Ocean Systems Center (NOSC), Code 911 Digital Dynamics Processor (DDP) is described. The DDP is a multiprocessor system designed for high speed numerical calculation. This system implements a new variation of common memory in order to allow a far greater number of processors than found currently on a TCDS. The conceptual design of the DDP was done in mid and late 1984 by Jack Zyphur. A variation of this design was implemented in hardware by Mitchell (1989) in early 1985. The first prototype was only two processor slaves, a repeater slave, and a master. Since the original goal of the DDP was to replace an EAI 8800 Analog computer, the first attempt at software for the DDP was a simulation language consisting of assembly language modules that would do the favor of direct equation implementation using a C cross-compiler that run on the master. In early 1987 Murphy programmed in a quaternion algorithm and the DDP proved operational in the NOSC Hybrid-Simulator. The DDP has since been up graded to six processor slaves running GRA MC68030 CPUs at 25 MHz. N89-29087# Johns Hopkins Univ., Baltimore, MD. Dept. of Mathematical Sciences. LARGE SCALE FUNCTION MINIMIZATION Final Scientific Report, 15 Jul. 1985 - 14 Oct. 1988 Stephen G. Nash 14 Oct. 1988 5 p (Grant AF-AFOSR-0222-85; AF Proj. 2304) (AD-A207718; AFOSR-89-0532TR) Avail: NTIS HC A02/MF A01 CSCL 12/2 Several new optimization techniques suitable for parallel computers have been developed and have been tested on an Intel hypercube. On a number of nonlinear problems, the algorithms tested have demonstrated dramatic speed-ups over their sequential counterparts. The fact that these speedups are better than can be attributed to parallelism suggests that they may lead to improved GRA sequential methods. N89-29088# Stanford Univ., CA. Dept. of Computer Science. INFORMATION REQUIREMENTS AND THE IMPLICATIONS FOR PARALLEL COMPUTATION Ph.D. Thesis Patrick H. Worley Jun. 1988 149 p (Contracts N00014-75-C-1132; DE-AC05-84OR-21400) (AD-A207802; SU-STAN-CS-88-1212) Avail: NTIS HC A07/MF A01 CSCL 12/1 The best serial algorithms for numerically approximating the solution of a linear partial differential equation (PDE) exploit knowledge of the solution operator. This dissertation describes how the solution operator also influences the behavior of parallel algorithms. Approximating the solution at a single location in the problem domain is considered. A lower bound on the error in the approximation is derived that is a function of the amount of data used and the smoothness of the data functions. From this one can derive a lower bound on the parallel complexity of algorithms that approximate the solution. The lower bound is a linear function of log 1/epsilon, where epsilon is an upper bound on the error. Thus the parallel complexity increases as epsilon decreases, independent of the number of processors used. An algorithm is also constructed whose parallel complexity is of this form, proving that the form of the bound is the best possible. The execution time of parallel algorithms is a function of both the communication costs and the parallel complexity. We describe bounds on the communication cost of parallel algorithms that are functions of the distance between collaborating processors. N89-29089# Stanford Univ., CA. Computer Systems Lab. ANALYSIS OF CACHE INVALIDATION PATTERNS IN MULTIPROCESSORS Wolf-Dietrich Weber and Anoop Gupta 1989 20 p (Contract N00014-87-K-0828) (AD-A207820) Avail: NTIS HC A03/MF A01 CSCL 12/5 on GRA To make shared-memory multiprocessors scalable, researchers are now exploring cache coherence protocols that do not rely on broadcast, but instead send invalidation messages to individual caches that contain stale data. The feasibility of such directory-based protocols is highly sensitive to the cache invalidation patterns that parallel programs exhibit. In this paper, we analyze the cache invalidation patterns caused by several parallel applications and investigate the effect of these patterns a directory-based protocol. Our results are based on multiprocessor traces with 4, 8 and 16 processors. To get insight into what the invalidation patterns would look like beyond 16 processors, we propose a classification scheme for data objects found in parallel applications and link the invalidation traffic patterns observed in the traces back to these high-level objects. Our results show that synchronization objects have very different invalidation patterns from those of other data objects. A write reference to a synchronization object usually causes invalidations in many more caches. We point out situations where restructuring the application seems appropriate to reduce the invalidation traffic, and others |