A taxonomy for computer architectures

A taxonomy is presented that extends M.J. Flynn's (IEEE Trans.Comput., vol. C-21, no.9, p.948-60, Sept. 1972), especially in the multiprocessor category. It is a two-level hierarchy in which the upper level classifies architectures based on the number of processors for data and for instructions and the interconnections between them. A lower level can be used to distinguish variants even more precisely; it is based on a state-machine view of processors. The author suggests why taxonomies are useful in studying architecture and shows how this applies to a number of modern architectures     

Real-time specification using Lucid

A methodology is presented for transforming a functional specification written in Lucid to an equivalent specification that captures its real-time properties. The enhanced specification consists of a set of equations that can be solved for several properties, including execution time and external requirements, or may simply be checked for the existence of a solution. Lucid has a set of meaning-preserving transformations, and a proof system corresponding to a behavioral semantics has been constructed. Both of these tools can be used to reason about properties of the specification. The specification is executable and can be used as a prototype for the system being specified. It is possible to express architectural constraints within the same formal framework. Thus this type of specification can be used to guide the development of new real-time systems     

Parallel Implementation of Tree Skeletons

Trees are a useful data type, but they are not routinely included in parallel programming systems, in part because their irregular structure makes partitioning and scheduling difficult. We present a method for algebraically constructing implementations of tree skeletons, high-level homomorphic operations that execute in parallel. Many computations on binary trees can be performed inO(logn) parallel time usingnprocessors, even taking account of communication costs. We extend these results to trees with arbitrary and variable degree. Then we show that it is possible to implement a distributed version of homomorphisms on binary trees, takingO(n/p+ log²p) parallel time onp < nprocessors, for trees of any skew and taking full account of communication costs. Under slightly stronger restrictions on the underlying functions, this can be improved toO(n/p+ logp). Furthermore, the technique for deriving distributed versions is algebraic, allowing the automatic generation of code for SPMD and data-parallel architectures.     

Computational approaches to suspicion in adversarial settings

Intelligence and law enforcement agencies collect large datasets, but have difficulty focusing analyst attention on the most significant records and structures within them. We address this problem using suspicion, which we interpret as relevant anomaly, as the measure associated with data records and individuals. For datasets collected about widespread activities in which the signs of adversarial activity are rare, we suggest ways to build predictive models of suspicion. For datasets collected as the result of lawful interception, we suggest a model of suspicion spreading using the social network implied by the intercepted data.     

Architecture-independent parallel computation

The major parallel architecture classes are considered: single-instruction multiple-data (SIMD) computers, tightly coupled multiple-instruction multiple-data (MIMD) computers, hypercuboid computers and constant-valence MIMD computers. An argument that the PRAM model is universal over tightly coupled and hypercube systems, but not over constant-valence-topology, loosely coupled-system is reviewed, showing precisely how the PRAM model is too powerful to permit broad universality. Ways in which a model of computation can be restricted to become universal over less powerful architectures are discussed. The Bird-Meertens formalism (R.S. Bird, 1989), is introduced and it is shown how it is used to express computations in a compact way. It is also shown that the Bird-Meertens formalism is universal over all four architecture classes and that nontrivial restrictions of functional programming languages exist that can be efficiently executed on disparate architectures. The use of the Bird-Meertens formalism as the basis for a programming language is discussed, and it is shown that it is expressive enough to be used for general programming. Other models and programming languages with architecture-independent properties are reviewed     

Molecular weight and solution viscosity characterization of PVC

As a means of developing the most accurate possible Mark-Houwink relationship possible for PVC, the literature Mark-Houwink coefficients for the weight average molecular weight (M_W) of PVC in THF are plotted and the derived “grand average” Mark-Houwink relationship (K = 15.56 × 10^?3 ml/g, a = 0.7690) is shown. High pressure-size exclusion chromatography (HP-SEC) data from two independent laboratories was used along with the “grand average” Mark-Houwink coefficients to calculate absolute number of average molecular weight (M_N) and weight average molecular weight values for PVC. An easy-to-use table has been developed to detail the relationships between M_N, M_W, K value, and inherent viscosity (I. V.).     

Coordinating Programs in the Network of Tasks Model

The Network of Tasks (NOT) model allows adaptive node programs written in a variety of parallel languages to be connected together in an almost acyclic task graph. The main difference between NOT and other task graphs is that it is designed to make the performance of the graph predictable from knowledge of the performance of the component node programs and the visible structure of the graph. It can therefore be regarded as a coordination language that is transparent about performance. For large-scale computations that are distributed to geographically-distributed compute servers, the NOT model helps programmers to plan, assemble, schedule, and distribute their problems.     

Distributed prediction from vertically partitioned data

We address the problem of prediction of data that is vertically partitioned, that is where local sites hold some of the attributes of all of the records. This situation is natural when data is collected by channels that are physically separated. For distributed prediction, we show that a technique called attribute ensembles is simple, predicts almost as well as a centralized predictor, reduces the amount of communication required, distributes computation and data access well, and allows each local site to keep its raw data private. We show how to extend attribute ensembles to data that is partitioned both horizontally and vertically.