Digital Commons Network^™

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 10, Number 2, February 1994, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A twelve page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

Using Tickets To Enforce The Serializability Of Multidatabase Transactions, Dimitrios Georgakopoulos, Marek Rusinkiewicz, Amit P. Sheth

Kno.e.sis Publications

To enforce global serializability in a multidatabase environment the multidatabase transaction manager must take into account the indirect (transitive) conflicts between multidatabase transactions caused by local transactions. Such conflicts are difficult to resolve because the behavior or even the existence of local transactions is not known to the multidatabase system. To overcome these difficulties, we propose to incorporate additional data manipulation operations in the subtransactions of each multidatabase transaction. We show that if these operations create direct conflicts between subtransactions at each participating local database system, indirect conflicts can be resolved even if the multidatabase system is not aware of …

Comet: A Synthetic Benchmark For Message-Passing Architectures, Nalini Ganapati, Steve Otto, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Rapid advances in hardware technology have led to wide diversity in parallel computer architectures. This diversity makes it difficult to evaluate or compare the performance of different parallel computers. Existing benchmarks tend either to be too architecture-specific, or too high-level. Both problems can result in benchmarks that not only provide insufficient information on the performance characteristics of the computer being tested, but are also difficult to port. New benchmarking approaches are needed for new architectural classes, particularly distributed-memory, message-passing computers. This paper focuses on benchmarking distributed-memory message-passing computers. A synthetic benchmark called CoMet (COmmunication METrics), is presented. CoMet is based …

An Algorithmic Palette Tool, Gary R. Greenfield

Department of Math & Statistics Technical Report Series

Our algorithmic tool follows the model of RGB percentage curves, but now the control of these curves is though algorithms that indirectly, and more abstractly, create, evolve, and modify such curves. To fully explain our methods we must first introduce the topic "mutating expressions." This is done in Section Two. In Section Three we document the user-interface problems we dealt with, and finally in Section Four discuss conclusions and suggest ideas for future exploration. Before commencing with the technical details however, we wish to emphasize the nature of the "colorization" problem that led to the conception and development of our …

Towards Feature Attachment, Xiangping Chen, Christoph M. Hoffmann

Department of Computer Science Technical Reports

No abstract provided.

Cooperating Brokers To Support Cooperative Work, Vinod Anupam, Chandrajit Bajaj, Peinan Zhang

Department of Computer Science Technical Reports

No abstract provided.

Experiences With Tripwire: Using Integrity Checkers For Intrusion Detection, Gene H. Kim, Eugene H. Spafford

Department of Computer Science Technical Reports

No abstract provided.

Generic Naming In Generative, Constraint- Based Design, Vallis Capoyleas, Xiangping Chen, Christoph M. Hoffmann

Department of Computer Science Technical Reports

No abstract provided.

An Application Of Pattern Matching In Intrusion Detection, Sandeep Kumar, Eugene H. Spafford

Department of Computer Science Technical Reports

No abstract provided.

Implementation Of An Automatic Mapping Tool For Massively Parallel Computing, Ajitha Gadangi

Theses

In this thesis, an implementation of a generic technique for fine grain mapping of portable parallel algorithms onto multiprocessor architectures is presented. The implemented mapping algorithm is a component of Cluster-M. Cluster-M is a novel parallel programming tool which facilitates the design and mapping of portable softwares onto various parallel systems. The other components of Cluster-M are the Specifications and the Representations. Using the Specifications, machine independent parallel algorithms are presented in a "clustered" fashion specifying the concurrent computations and communications at every step of the overall execution. The Representations, on the other hand, are a form of clustering the …

Graphical Oodb Modeling For Medical Information Standards (Gommis), Jiping Liu

Theses

The graphical representation of database schemata has been a useful tool for the designer and users of database systems. Such a tool for OODB schemata should incorporate a wide variety of symbols which cover most concepts of existing Object-Oriented Database (OODB), so it is sufficient to support a diverse group of object-oriented data models.

In this paper we created a. graphical representation, using the OOdini system and language, of the European Prestandard for Medical Informatics on Message Exchange of Laboratory Information. This European Prestandard describes a standardized format for messages to be exchanged between a. health care provider and a …

Graphical Oodb Modeling For Medical Information Standards (Gommis), Nagesh K. Puppala

Theses

Our task is to create a graphical representation of the European Prestandard for Medical Informatics on Message Exchange of Laboratory Information. This document, made available to us through Columbia Presbyterian, describes a standardized format for messages to be exchanged between a healthcare provider and a medical laboratory. The prestandard represents important information in a very disconnected way.

We have used OODINI system and language to develop our GOMMIS system. OODINI is a graphical editor for object-oriented database schemas that was developed at NJIT during the past three years. OODINI features a poweful set of icons that cover most concepts of …

Concurrent Use Of Two Programming Tools For Heterogeneous Supercomputers, Javier G. Vasquez

Theses

In this thesis, a demostration of the heterogeneous use of two programming paradigms for heterogeneous computing called Cluster-M and HAsC is presented. Both paradigms can efficiently support heterogeneous networks by preserving a level of abstraction which does not include any architecture mapping details. Furthermore, they are both machine independent and hence are scalable. Unlike, almost all existing heterogeneous orchestration tools which are MIMD based, HAsC is based on the fundamental concepts of SIMD associative computing. HAsC models a heterogeneous network as a coarse grained associative computer and is designed to optimize the execution of problems with large ratios of computations …

Authentication For Mobile Computing, Andreas Keppler

Theses

Host mobility is becoming an increasingly important feature with the recent arrival of laptop and palmtop computers, the development of wireless network interfaces and the implementation of global networks. Unfortunately, this mobile environment is also much more vulnerable to penetration by intruders. A possible means of protection can be authentication. This guarantees the identity of a communication peer.

This thesis studies the constraints imposed on the mobile environment with respect to authentication. It compares the two prevailing authentication mechanisms, Kerberos and SPX, and tries to make suggestions of how a mechanism can be adapted to the mobile environment.

Design And Implementation Of Ipis : An X-Window Based Image Processing Interactive System, Eduardo Morales

Theses

Most of image processing systems are based on command line functions or can only display one image at a time. This is a serious inconvenience for those who need an interactive system session or want to compare two images processed by different techniques at the same time.

The system was designed with these problems in mind. It is able to display the processed image right after an operation and to display several images simultaneously, making it simple to compare techniques. The system was also created with the purpose to be used in an academic environment. Its structured design makes it …

A Pipeline Implementation Of Lu-Decomposition On A Hypercube, Scott Thibault, Lenore Mullin

Computer Science Technical Reports

This paper presents a method of performing LU-Decomposition on a hypercube. The algorithm is constructed similar to the way a pipeline would be used in hardware or on a systolic array processor. Using this method eliminates the need to broadcast data to all the processors at each iteration of the algorithm. Communication takes place at each iteration but since we are using a pipeline model, the communication is between each processor and the next processor in the pipeline. On the hypercube this communication can be done in parallel by using the Gray code ordering to embed a ld mesh (pipeline) …

Formal Methods For Portable, Scalable, Scheduling, Routing And Communication Protocol, Lenore M. R. Mullin, Scott A. Thibault, Daria R. Dooling, Erik A. Sandberg

Computer Science Technical Reports

The PRAM model has been shown to be an optimal design for emulating both loos and tightly coupled multiprocessors for unit time operations. Extensions to this design employ software pipelining on a network of homogeneous workstations. Partitioning array data structures and pipelining groups of partitions to processors can minimize latency and bottlenecking on distributted message passing multiprocessing architectures. Our previous paper developed a general message passing design that was conjectured to port to a CMS and scale to more processors connected via TCPIP protocol. This paper presents the results of of our ported and scaled designs. We have indeed developed …

Effective Data Parallel Computation Using The Psi Calculus, L. R. Mullin, M. A. Jenkins

Computer Science Technical Reports

No abstract provided.

Efficient Run-Time Assurance In Distributed Systems Through Selection Of Executable Assertions, Martina Schollmeyer, Bruce Mcmillin

Computer Science Technical Reports

Run-time assurance of a distributed system can be obtained by comparing, at run-time, the behavior of the program with the expected behavior described in the program's specification. Executable assertions, embedded into the program code, can determine when there are discrepancies, due to processor failures, between actual and expected behavior. Thus, there is no global monitoring scheme but processes will check each other.

A non-faulty process will always perform correct computation. It can detect errors in other processes after receiving information from them and checking it against expected values by using executable assertions. In order to efficiently check programs at run-time, …

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.

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 …

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 …

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 …

Design Issues For The Parallelization Of An Optimal Interpolation Algorithm, Gregor Von Laszewski, Mike Seablom, Miloje Makivic, Peter Lyster

Northeast Parallel Architecture Center

A regionalized optimal interpolation algorithm is currently used at the NASA Goddard Data Assimilation Office (DAO) for four dimensional data assimilation. Instead of using all observations regions are defined to approximate the solution. The sequential code for the regionalized optimal interpolation is very complex and in its current form unusable for MIMD machines. This paper describes the efforts at the DAO to parallelize the existing sequential algorithm. We outline three strategies transforming the sequential algorithm gradually to MIMD machines. A major requirement for the new parallel algorithm is the portability to as many MIMD machines as possible. Therefore, the parallel …

A Generalized Expression Optimization Hook For C++ On High-Performance Architectures, David J. Edelsohn

Northeast Parallel Architecture Center

C++ has gained broad acceptance as an object-oriented evolutionary extension to the C language, but it severely constrains methods for operating on class objects by forcing all data manipulation through an interface which assumes that all basic operations can be implemented as they are written: as unary or binary operators. C++ allows great flexibility in the creation of complex data structures which can perform the same functionality as built-in types of many other languages, but unfortunately it does not allow an equivalent level of flexibility so that operators acting on those data types can achieve the same level of efficiency …

On The Noninterpolation Of Polyhedral Maps, Adrian Riskin, D.W. Barnette

Mathematics

In this paper we show that if attention is restricted to polyhedral embeddings of graphs, no theorem analogous to the Duke interpolation theorem for 2-cell embeddings is true. We also give two interesting classes of graphs: (i) a class in which the members have polyhedral embeddings in the torus and also in orientable manifolds of arbitrarily high genus, (ii) and another in which the members have polyhedral embeddings in the projective plane and also in orientable and nonorientable manifolds of arbitrarily low Euler characteristic.