Search

This is a progress report on ARPA contract DAHC04-72-C-0001, entitled, 'ILLIAC 4 Applications Research at the Center for Advanced Computation, University of Illinois at Urbana-Champaign.' During this period there was research in the following areas: (1) Applied mathematics, (2) Pictorial pattern information processing, (3) Distributed computer systems, and (4) Network terminal systems., See also AD772511. Report on ILLIAC IV Applications Research.

During this period work was performed in the following areas: (1) Development of numerical techniques suitable for parallel processing; (2) ILLIAC IV multispectral image processing; (3) Research in distributed computational systems of heterogeneous computers; (4) Research and development of network access., See also report dated 31 Mar 1974, AD786172.

A space object position prediction program was implemented on the STARAN associative array processor (AP) installed at the Rome Air Development Center (RADC), New York. This document outlines the experience gained from this task. A section is devoted to an analysis of the time and effort required to implement the program. Emphasis is given to the program design and array layout phase. Systematic (i.e., independent of the specific program) and application- related capabilities and limitations are discussed. An analysis of the RADCAP system from a user's viewpoint is also presented. The latter part of the paper deals with recommendations for an approved STARAN system (hardware and software) and an improved host computer interface.

The mathematical foundation and the various practical aspects of the numerical solution of gas dynamic equations are critically reviewed with emphasis on obtaining quantitatively accurate solutions for application in various engineering and sciences. Computational stability rate of convergence and accuracy (or error estimate) are discussed. The promises and problems of the 4th generation computers are outlined within this perspective. Computational stability shoud not be obtained at the sacrifice of the convergence rate to and the accuracy of the final solution. With accuracy in mind, the explicit algorithms are likely preferrable to the implicit ones. Strict conservation of the difference formulation is recommended and exemplified to avoid the accumulation of local truncation errors and to facilitate the estimate of the errors in a steady state solution. Illustrative examples are given including supersonic flows with shocks. (Author)

A critical element of any low or medium bit rate (< 16 kbps) speech digitization system is the pitch extraction and voicing mechanism. Any digitization system in this low to medium bit rate region will require a good pitch extraction technique as a key part of the system. In this study previous pitch extraction techniques are reviewed in the light of current pitch extraction requirements for speech digitization. Two promising new pitch extraction algorithms are suggested: the multiband pitch period estimation technique and the skip-sample recursive least squares pitch position estimation technique. The former gives only spacings between pitch pulses, while the latter gives registration of the pitch pulses with the speech waveform.

The behavior of the vector recurrence y sub (n+1) = M(y sub n) + w sub (n+1) is studied under very weak assumptions. Let lambda (M) denote the spectral radius of M and let lambda (M) > or = 1. Then if the w sub n are bounded in norm and a certain subspace hypothesis holds, the root order of the (y sub n) is shown to be lambda (M). If one additional hypothesis on the dimension of the principal Jordan blocks of M holds, then the quotient order of the (y sub n) is also lambda (M). The behavior of the homogeneous recurrence is studied for all values of lambda (M). These results are applied to the analysis of: Nonlinear iteration with application to iteration with memory and to parallel iteration algorithms; Order and efficiency of composite iteration; The power method., Prepared in cooperation with Arizona State Univ., Tempe. Dept. of Mathematics. Sponsored in part by National Aeronautics and Space Administration, Langley Station, Va. Langley Research Center. Grant NGR-47-102-001.

The rough design of a semantically directed vision processor has been presented in an earlier paper. The current paper outlines the progress in developing the stages of early visual processing in that system. It describes a parallel structure, a computational 'preprocessing cone,' which transforms and reduces large amounts of visual data in a layered fashion.

The problem of solving triangular linear systems of size n on a parallel computer with small parallelism is considered. Assume that the time is measured by the number of parallel steps of any arithmetic operation. It is shown that the problem can be done in time n squared/k + O(n) with k processors for k < or = O(n), O(n sup (2-r) log n) with O(n sup r) processors for 1 < r < 3/2, and O(n sup (1-r/3) (log sup 2)n) with O(n sup r) processors for 3/2 < or = r < or = 3. The results are obtained by using two principles of reducing parallel algorithms with large parallelism to parallel algorithms with small parallelism. The two principles for the reduction are expected to be useful for other problems., Sponsored in part by Institut de Recherche d'Informatique et d'Automatique, Le Chesnay (France).

Contents: The discrete-ordinates method for the transport equation; The numerical solution of the equations for rotating stars; Automatic solution of differential equations; Integral operators for parabolic equations and their application; Galerkin methods for modeling gas pipelines; The application of sparse matrix methods to the numerical solution of nonlinear elliptic partial differential equations; Collocation solutions of integro-differential equations; On Dirichlet's problem for quasilinear elliptic equations; The numerical solution of some elliptic boundary value problems by integral operator methods; Iterative schemes for elliptic systems; Extrapolation in the finite element method with penalty; Transonic design in two dimensions; Approximate regularized solutions to improperly posed linear integral and operator equations; A majorization technique for hyperbolic equations; Boundary layer methods for ordinary differential equations with small coefficients multiplying the highest derivatives; Fixed point iterations using infinite matrices, 2; The line method for parabolic differential equations, problems in boundary layer theory and existence of periodic solutions; An integral equation method for generalized analytic functions; Solving partial differential equations using ILLIAC 4., Report on Lecture Notes in Mathematics, v430. Library of Congress Catalog Card No. 74-28189.

The report is a collection of Working Papers in Speech Recognition on the following topics: Organization of the HEARSAY II speech understanding system; The DRAGON system -- an overview; Parameter-independent machine segmentation and labeling; A new time-domain analysis of fricatives and stop consonants; Sub-lexical levels in the HEARSAY II speech understanding system; Inference and use of simple predictive grammars; Real-time linear predictive coding of speech on the SPS-41 microprogrammed triple-processor system; A 16-bit A-D-A conversion system for high-fidelity audio research., Sponsored in part by DARPA. See also report dated Aug 1973, AD0770633.

This report documents the achievements from 1 July 1973 to 1 July 1974 of continuing research for the development and application of mathematical techniques for the analysis and optimization of computer systems. The material covers the following areas: performance evaluation, parallel processing, data management systems, associative processors, languages for parallel processors, machine instruction sets.

The purpose of this thesis was to devise algorithms for the extraction of syntactic features within a binary-valued array processor with small neighborhoods. Simulations demonstrated the success of these algorithms and emphasized the advantages of keeping image processing within the parallel part of a recognition system.

Research under this grant was concerned with computer graphics and image processing, and consisted of the following 7 specific investigations: (1) development of efficient algorithms for line-drawing processing, (2) optimum two-dimensional layout, (3) discrete-time systems with parallel processes, (4) solution of the hidden-line problem for curved objects, (5) data structures for computer graphics, (6) the computer reconstruction or three-dimensional objects from multiple two-dimensional projections, and (7) detection of edges in noisy photographs. A list of publications resulting from the work is included.

A new parallel algorithm for the solution of a general linear recurrence is described. Its relation to the work of Kogge and Stone is discussed., Sponsored in part by Grant NSF-GJ-32111.

This document describes a preliminary version of a long period array processing package designed around the FKCOMB algorithm for use on the ILLIAC 4 computer. FKCOMB is a general-purpose array-processing program that uses frequency-wavenumber analysis to produce a bulletin which lists signal detections and various statistics for each detection. Two data editing and reformatting modules prepare the seismic data for FKCOMB and can be modified for use with other seismic algorithms. Preliminary reformatting of the seismic data is performed by DEM1. The data is edited and fast fourier transformed by DEM2. The input parameters required for operating these programs and their subroutines are described in this document.

Two features of the ILLIAC IV system at NASA/Ames are particularly appropriate to the processing of seismic data. One is its ability to apply a given algorithm to sixty-four different data streams simultaneously, thus providing an order of magnitude increase in processing speed over conventional machines. The second is its large data storage. The seismological algorithms for convolution filtering, beamforming, matched filtering, PHILTRE, maximum likelihood, and FKCOMB are each able to take advantage of these features in the processing of seismic data. The data can be arranged so that each processing element contains successive time windows on a given trace, as in bandpass filtering, or successive beam sets, as in beamforming.

Algorithms to find a simple root alpha of a continuous function f are considered which are suitable for implementation on an array type of parallel processing computer using N processing elements. (Modified author abstract)

The reason for building the ILLIAC 4 is to provide a computer which lends itself to the solution of partial differential equations, to matrix manipulation, as well as to solutions of other problems. ILLIAC 4 consists of a set of 64 processing elements (PE's) which follow a single instruction sequence under the control of a control unit. Each PE has its own memory, but communication between PE's is provided through a special routing register. The user of ILLIAC must recognize these constraints and special properties and be willing to expend some effort in order to use the machine effectively for a particular problem. A reasonable approach to solving problems on this computer, to do preliminary experiments, developments, and debugging on a conventional computer, and then implement a 'refined' version of the computer program on ILLIAC 4 itself. (Author)

Edited trans. of Upravlyayushchie Sistemy i Mashiny (USSR) v1 n2 p89-94 Mar-Apr 73, by Victor Mesenzeff.

A generative 2-dimensional rectangular array model which allows for growth only along the edges is proposed. The growth takes place in parallel, restricted by tables, and growth along the four different edges is controlled by a control set. A special class of these models includes 2-dimensional developmental systems; the hierarchy within this class is studied. The generative power of the new model is compared with that of earlier array models.

During this period there was research in the following areas: Development of numerical techniques suitable for parallel processing in the areas of linear programming, algebraic eigenvalue, and approximation of functions; ILLIAC 4 multispectral image processing; enhancements to the PEESPOL compiler; network terminal systems project; and, distributed computational systems of heterogeneous computers., See also report dated 1 May 1973, AD763290. Report on ILLIAC IV Applications Research.

General algorithmic specification, not including detailed logical design, of a highly parallel, specially organized cellular machine to embody a discrete Kalman filter is described. Various matrix operation algorithms and comparisons to sequential operations are given. Parallel computation is based on a square array of identical, limited capability modules, providing inherent speed and taking advantage of current LSI technology. The time to process increases about linearly with problem size rather than as the cube. Simulation results of a tracking problem posed by Naval Electronics Laboratory, San Diego, are included. The problem is one of a linear plant with a nonlinear observation. Thus a dynamic linearization of the observation matrix is required, such dynamics pervading the entire filter. (Author)

The report summarizes the results of a two-year research program undertaken to investigate aspects of reliability of computer systems particularly with regard to theoretical aspects of their design and performance in Air Force applications. Major portions of the work were concerned with theoretical studies of image processing, pattern recognition, and computer models of unknown systems (identification). However, some studies investigated design of reliable logical hardware, computer software, and multiprocessor resource allocation modes.

Contents: Generalized multicomponent systems under cannibalization; A Bayesian approach to demand estimation and inventory provisioning; Readiness and the optimal redeployment of resources; On max-min problems; A theory of ideal linear weights for heterogeneous combat forces; Decision rules for attacking targets of opportunity; Target selection in lanchester combat: linear- law attrition process; An N-step, 2-variable search algorithm for the component placement problem; Parametric linear programming: some special cases; Sequential search of an optimal dosage: non-Bayesian methods; Further light on nonparametric selection efficiency; Alternate methods of project scheduling with limited resources; Scheduling with parallel processors and linear delay costs., See also Volume 20, Number 3, AD-772 444.

The main goal of this thesis is to study the performance tradeoffs between parallelism and increased concurrency control overhead during simultaneous user updates of a database. During such updates, a database management system must guarantee that the multiple users do not interfere with each other. The potential advantages of parallelism in accessing a database include the better utilization of computer resources and better response times for users. Those advantages, however, may be offset by the increased use of system resources to insure that there is no interference between the multiple users. In a distributed database, the data is stored on different computer sites connected through some type of network. In a distributed database, increased parallelism is possible during simultaneous database activities. However, the concurrency control overhead may also increase. The simulations modeled a variety of concurrency control algorithms to study the additional tradeoffs in a distributed database. The simulation results indicated that with a high speed network and mostly local database activities, either concurrency control approach is acceptable. As the network becomes slower, the decentralized control algorithms are preferable. If most of the database activities are distributed, however, the primary site approach can take advantage of its global knowledge to better schedule the processing of transactions and thus provide better performance than the decentralized algorithms.

This monograph includes most of the results to date of our analysis of the geometric ability of linear separation machines. We expect soon to publish the complete work as a book: the complete version will contain further results on learning and on some relation between parallel and serial algorithms. Topics include: Algebraic Theory--Theory of Boolean linear separation functions, Group theory of linear predicates, Some special predicates, and The 'And-Or' Theorem; Geometric Theory--Connectivity and topological properties, Geometric patterns of low order, Normalization and stratification, and The Diameter- limited perceptron; and Magnitude of the Coefficients.