Physical Sciences and Mathematics Commons^™

Logic Simulation Using An Asynchronous Parallel Discrete-Event Simulation Model On A Simd Machine, Sharad C. Seth, Lee Gowen, Matt Payne, Don Sylwester

CSE Conference and Workshop Papers

The Chandy-Misra-Bryant (CMB) model has been applied to logic simulation of synchronous sequential circuits using a massively parallel SIMD computer, a CM-2 Connection Machine. Several methods of reducing message traffic in a logic simulation have been adapted to the SIMD architecture of the CM-2, with the result that each method of reducing message traffic actually decreases the speed of the simulation. This suggests that communication costs required to support logic simulation are small compared to the cost of deciding which messages need not be sent.

Projective Plane Embeddings Of Polyhedral Pinched Maps, Adrian Riskin

Mathematics

We give various conditions on pinched-torus polyhedral maps which are necessary for their graphs to be embeddable in the projective plane. Our other main result is that even if the graph of a polyhedral map in the pinched torus is embeddable in a projective plane, the map induced by the embedding cannot be polyhedral, but must have all faces bounded by cycles. Finally, we give a class of examples of graphs which have polyhedral embeddings on the pinched torus and also on orientable surfaces of arbitrary high genus.

Theology And Interpretation: A Footnote To Mcluhan, David Morgan Lochhead

Dr. David Morgan Lochhead

An exploration of the impact of electronic text on hermeneutics. Lochhead argues that electronic text processing undermines the stability of meaning that is associated with the printed word.

A Data Parallel Algorithm For Solving The Region Growing Problem On The Connection Machine, Nawal Copty, Sanjay Ranka, Geoffrey C. Fox, Ravi V. Shankar

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

Region growing is a general technique for image segmentation, where image characteristics are used to group adjacent pixels together to form regions. This paper presents a parallel algorithm for solving the region growing problem based on the split and merge approach, and uses it to test and compare various parallel architectures and programming models. The implementations were done on the Connection Machine, models CM-2 and CM-5, in the data parallel and message passing programming models. Randomization was introduced in breaking ties during merging to increase the degree of parallelism, and only one and two-dimensional arrays of data were used in …

The Complexity Of Local Stratification, Peter Cholak, Howard A. Blair

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

The class of locally stratified logic programs is shown to be Π 1 1-complete by the construction of a reducibility of the class of infinitely branching nondeterministic finite register machines.

Genetic Algorithms For Graph Partitioning And Incremental Graph Partitioning, Harpal Maini, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

Partitioning graphs into equally large groups of nodes, minimizing the number of edges between different groups, is an extremely important problem in parallel computing. This paper presents genetic algorithms for suboptimal graph partitioning, with new crossover operators (KNUX, DKNUX) that lead to orders of magnitude improvement over traditional genetic operators in solution quality and speed. Our method can improve on good solutions previously obtained by using other algorithms or graph theoretic heuristics in minimizing the total communication cost or the worst case cost of communication for a single processor. We also extend our algorithm to Incremental Graph Partitioning problems, in …

The Transportation Primitive, Ravi V. Shankar, Khaled A. Alsabti, Sanjay Ranka

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

This paper presents algorithms for implementing the transportation primitive on a distributed memory parallel architecture. The transportation primitive performs many-to-many personalized communication with bounded incoming and outgoing traffic. We present a two-stage deterministic algorithm that decomposes the communication with possibly high variance in message size into two communication stages with low message size variance. If the maximum outgoing or incoming traffic at any processor is t, transportation can be done in 2t¯ time (+ lower order terms) when t O(p 2 + pø=¯) (¯ is the inverse of the data transfer rate, ø is the startup overhead). If the maximum …

Parallel Incremental Graph Partitioning Using Linear Programming, Chao Wei Ou, Sanjay Ranka

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

Partitioning graphs into equally large groups of nodes while minimizing the number of edges between different groups is an extremely important problem in parallel computing. For instance, efficiently parallelizing several scientific and engineering applications requires the partitioning of data or tasks among processors such that the computational load on each node is roughly the same, while communication is minimized. Obtaining exact solutions is computationally intractable, since graph-partitioning is an NP-complete. For a large class of irregular and adaptive data parallel applications (such as adaptive meshes), the computational structure changes from one phase to another in an incremental fashion. In incremental …

Performance Modeling Of Load Balancing Algorithms Using Neural Networks, Ishfaq Ahmad, Arif Ghafoor, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

This paper presents a new approach that uses neural networks to predict the performance of a number of dynamic decentralized load balancing strategies. A distributed multicomputer system using any distributed load balancing strategy is represented by a unified analytical queuing model. A large simulation data set is used to train a neural network using the back–propagation learning algorithm based on gradient descent. The performance model using the predicted data from the neural network produces the average response time of various load balancing algorithms under various system parameters. The validation and comparison with simulation data show that the neural network is …

Random Data Accesses On A Coarse-Grained Parallel Machine Ii. One-To-Many And Many-To-One Mappings, Ravi V. Shankar, Sanjay Ranka

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

This paper describes deterministic communication-efficient algorithms for performing random data accesses with hot spots on a coarse-grained parallel machine. The general random access read/write operations with hot spots can be completed in Clanip (+ lower order terms) time and is optimal and scalable provided n _> O(pa+p2r/l) (n is the number of elements distributed across p processors, r is the start-up overhead and 1/It is the data transfer rate). C is a small constant between 3 and 4 for the random access write operation, slightly higher for the random access read operation. Monotonic random access reads/writes can be completed with …

Genetic Algorithms For Soft Decision Decoding Of Linear Block Codes, Harpal Maini, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

Soft-decision decoding is an NP-hard problem of great interest to developers of communication systems. We show that this problem is equivalent to the problem of optimizing Walsh polynomials. We present genetic algorithms for soft-decision decoding of binary linear block codes and compare the performance with various other decoding algorithms including the currently developed A* algorithm. Simulation results show that our algorithms achieve bit-error-probabilities as low as 0:00183 for a [104; 52] code with a low signal-to-noise ratio of 2:5 dB, exploring only 22; 400 code words, whereas the search space contains 4:5 \Theta 10 15 codewords. We define a new …

Scheduling Of Unstructured Communication On The Intel Ipsc/860, Jhy-Chun Wang, Sanjay Ranka

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

In this paper we present several algorithms for decomposing all-to-many personalized communication into a set of disjoint partial permutations. These partial permutations avoid node contention as well as link contention. We discuss the theoretical complexity of these algorithms and study their effectiveness both from the view of static scheduling and from runtime scheduling. Experimental results for our algorithms are presented on the iPSC/860.

Merlin's Magic Square Enhanced, Gary R. Greenfield

Department of Math & Statistics Technical Report Series

This paper first considers questions about games related to Merlin's Magic Square from the point of view of group actions. At this juncture, little beyond the formal model is new, but the exposition sets the stage for considering certain "enhanced" versions of these games. The analysis of enhanced games, with the aid of semigroup actions, is carried out in complete detail for an ostensibly simpler (k = 3) game before turning to a Merlin ( k = 4) game. Concluding sections discuss various ways to generalize our games.

To review the solution to Merlin's Magic Square, we begin by introducing …

Data Access Reorganizations In Compiling Out-Of-Core Data Parallel Programs On Distributed Memory Machines, Rajesh Bordawekar, Alok Choudhary, Rajeev Thakur

Electrical Engineering and Computer Science - All Scholarship

This paper describes techniques for translating out-of-core programs written in a data parallel language like HPF to message passing node programs with explicit parallel I/O. We describe the basic compilation model and various steps involved in the compilation. The compilation process is explained with the help of an out-of-core matrix multiplication program. We first discuss how an out-of-core program can be translated by extending the method used for translating in-core programs. We demonstrate that straightforward extension of in-core compiler does not work for out-of-core programs. We then describe how the compiler can optimize the code by (1) estimating the I/O …

Passion Runtime Library For Parallel I/O, Rajeev Thakur, Rajesh Bordawekar, Alok Choudhary, Ravi Ponnusamy

Electrical Engineering and Computer Science - All Scholarship

We are developing a compiler and runtime support system called PASSION: Parallel And Scalable Software for Input-Output. PASSION provides software support for I/O intensive out-of-core loosely synchronous problems. This paper gives an overview of the PASSION Runtime Library and describes two of the optimizations incorporated in it, namely Data Prefetching and Data Sieving. Performance improvements provided by these optimizations on the Intel Touchstone Delta are discussed, together with an out of -core Median Filtering application.

Optimal Processor Assignment For A Class Of Pipelined Computations, Alok N. Choudhary, Bhagirath Narahari, David Nicol, Rahul Simha

Electrical Engineering and Computer Science - All Scholarship

The availability of large scale multitasked parallel architectures introduces the following processor assignment problem: we are given a long sequence of data sets, each of which is to undergo processing by a collection of tasks whose inter-task data dependencies form a series-parallel partial order. Each individual task is potentially parallelizable, with a known experimentally determined execution signature. Recognizing that data sets can be pipelined through the task structure, the problem is to find a "good" assignment of processors to tasks. Two objectives interest us: minimal response time per data set given a throughput requirement, and maximal throughput given a response …

Passion: Parallel And Scalable Software For Input-Output, Alok Choudhary, Rajesh Bordawekar, Michael Harry, Rakesh Krishnaiyer

Electrical Engineering and Computer Science - All Scholarship

We are developing a software system called PASSION: Parallel And Scalable Software for Input-Output which provides software support for high performance parallel I/O. PASSION provides support at the language, compiler, runtime as well as file system level. PASSION provides runtime procedures for parallel access to files (read/write), as well as for out-of-core computations. These routines can either be used together with a compiler to translate out-of-core data parallel programs written in a language like HPF, or used directly by application programmers. A number of optimizations such as Two-Phase Access, Data Sieving, Data Prefetching and Data Reuse have been incorporated in …

Job Scheduling In Rings, Perry Fizzano, Clifford Stein, David Karger, Joel Wein

Computer Science Technical Reports

We give distributed approximation algorithms for job scheduling in a ring architecture. In contrast to almost all other parallel scheduling models, the model we consider captures the influence of the underlying communications network by specifying that task migration from one processor to another takes time proportional to the distance between those two processors in the network. As a result, our algorithms must balance both computational load and communication time.

The algorithms are simple, require no global control, and work in a variety of settings. All come with small constant-factor approximation guarantees; the basic algorithm yields schedules of length at most …

Asymptotically Tight Bounds For Performing Bmmc Permutations On Parallel Disk Systems, Thomas H. Cormen, Thomas Sundquist, Leonard F. Wisniewski

Computer Science Technical Reports

We give asymptotically equal lower and upper bounds for the number of parallel I/O operations required to perform bit-matrix-multiply/complement (BMMC) permutations on parallel disk systems. In a BMMC permutation on N records, where N is a power of 2, each (lg N)-bit source address x maps to a corresponding (lg N)-bit target address y by the matrix equation y = Ax XOR c, where matrix multiplication is performed over GF(2). The characteristic matrix A is (lg N) x (lg N) and nonsingular over GF(2). Under the Vitter-Shriver parallel-disk model with N records, D disks, B records per block, and M …

The Design And Development Of Interactive Multimedia Conference Proceedings, Samuel A. Rebelsky, James Ford, Kenneth Harker, Fillia Makedon, P Takis Metaxas, Charles Owen

Computer Science Technical Reports

Many conferences are now providing electronic proceedings. Often, these proceedings are little more than electronic collections of documents put together in a standard software package, such as SuperBook or Acrobat. This means that few of these proceedings incorporate the full range of materials that a conference generates. Furthermore, because these general interfaces are not designed for conference proceedings, they do not provide all the features a conference warrants.

The interactive multimedia proceedings for the DAGS'92 Institute on Parallel Computation used an interface designed specifically for presenting conference materials and provided both talks (audio, video, and slides) and papers (in hypertext …

Scheduling In A Ring With Unit Capacity Links, Perry Fizzano, Clifford Stein

Computer Science Technical Reports

We consider the problem of scheduling unit-sized jobs on a ring of processors with the objective of minimizing the completion time of the last job. Unlike much previous work we place restrictions on the capacity of the network links connecting processors. We give a polynomial time centralized algorithm that produces optimal length schedules. We also give a simple distributed 2-approximation algorithm.

Vic*: A Preprocessor For Virtual-Memory C*, Thomas H. Cormen, Alex Colvin

Computer Science Technical Reports

This paper describes the functionality of ViC*, a compiler-like preprocessor for out-of-core C*. The input to ViC* is a C* program but with certain shapes declared \verb`outofcore`, which means that all parallel variables of these shapes reside on disk. The output is a standard C* program with the appropriate I/O and library calls added for efficient access to out-of-core parallel variables.

Strategies For The Parallel Training Of Simple Recurrent Neural Networks, Peter J. Mccann, Barry L. Kalman

All Computer Science and Engineering Research

Two concurrent implementations of the method of conjugate gradients for training Elman networks are discussed. The parallelism is obtained in the computation of the error gradient and the method is therefore applicable to any gradient descent training technique for this form of network. The experimental results were obtained on a Sun Sparc Center 2000 multiprocessor. The Sparc 2000 is a shared memory machine well suited to coarse-grained distributed computations, but the concurrency could be extended to other architectures as well.

An Application-Oriented Error Control Scheme For High Speed Networks, Fengmin Gong, Gurudatta Parulkar

All Computer Science and Engineering Research

Many new network applications demand interprocess communication (IPC) services that are not supported by existing transport protocol mechanisms. Large bandwidth-delay products of high-speed networks also render the existing control mechanisms such as flow and error control less efficient. In particular, new error control schemes that can provide variable degrees of error recovery according to the applications requirements are needed. This paper presents the design, evaluation, and implementation of an application-oriented error control scheme that is aimed at supporting efficient IPC in high-speed networking environments. Our results show that the proposed error control scheme allows effective control of trade-off between the …

Visual Presentation Of Software Specifications And Designs, Gruia-Catalin Roman, Delbert Hart, Charles Calkins

All Computer Science and Engineering Research

Formal methods hold the promise for high dependability in the design of critical software. However, software engineers who employ formal methods need to communicate their design decisions to users, customers, managers, and collegues who may not be in a position to acquire a full understanding of the formal notation being used. Visualizations derived from formal specifications and designs must be able to convey the required information precisely and reliably without the use of formal notation. This paper discusses a design methodology which attempts to integrate a design methodology based upon specification and program refinement with a state-of-the-art approach to rapid …

Reconstruction Of Surfaces And Surfaces- On-Surfaces From Unorganized Weighted Points, Chandrajit L. Bajaj, Fausto Bernardini, Guoliang Xu

Department of Computer Science Technical Reports

No abstract provided.

Maintaining Consistency In Multidatabase Systems: A Comprehensive Study, Aidong Zhang, Bharat K. Bhargava

Department of Computer Science Technical Reports

No abstract provided.

General Interior Hermite Collocation Methods For Second Order Elliptic Partial Differential Equations, Yu-Ling Lai, Apostolos Hadjidimos, Elias N. Houstis, John R. Rice

Department of Computer Science Technical Reports

No abstract provided.

Edge Weight Reduction Problems In Directed, Acyclic Graphs, Susanne E. Hambrusch, Hung-Yi Tu

Department of Computer Science Technical Reports

No abstract provided.

Principles And Realization Strategies Of Intregrating Autonomous Software Systems: Extension Of Multidatabase Transaction Management Techniques, Aidong Zhang, Bharat Bhargava

Department of Computer Science Technical Reports

No abstract provided.