Digital Commons Network^™

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 …

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 …

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, …

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 …

The Binational English & Spanish Telecommunications Network, Armando A. Arias Jr.

SSGS Faculty Publications and Presentations

BESTNET was established in the early 1980's, as an effort to link universities on both sides of the U.S.- Mexico border through microwave, satellite and cable television technologies. In the late 1980's BESTNET focused primarily on the development of asynchronous computer mediated learning and teaching in an internationally networked virtual environment. For the past six years (1990's) BESTNET has strengthened its binational ties and continued its "high tech" focus through the development of active or vibrant model technology which is assisting in the creation of an on-line binational university setting that is "borderless" (albeit, seamless to the user). Today, this …

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 …

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.

Tele-Assistance For Semi-Autonomous Robots, Erika Rogers, Robin R. Murphy

Computer Science and Software Engineering

This paper describes current work on a cooperative tele-assistance system for semi-autonomous robots. This system combines a robot architecture for limited autonomous perceptual and motor control with a knowledge-based operator assistant which provides strategic selection and enhancement of relevant data. The design of the system is presented, together with a number of exception-handling scenarios that were constructed as a result of experiments wit.h act.ual sensor data collected from two mobile robots.

The Multigraph Modeling Tool, Amy Apon, C A. Childers, W H. Hooper, K D. Gordon, L W. Dowdy

Publications

No abstract provided.

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 …

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.

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

School of Computing: 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.

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

BITs and PCs Newsletter

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

Linear Codes And Error-Correction, Karen Brown

Presidential Scholars Theses (1990 – 2006)

The process of encoding information for transmission from one source to another is a vital process in many areas of science and technology. Whenever coded information is sent, there arises a certain possibility that an error will occur, either during transmission or in decoding. Therefore, it is imperative to develop methods to detect and correct errors in a code. The study of coding theory is a "new" area of mathematics which is relatively undeveloped.

This paper focuses on the properties of linear codes -and their corresponding methods of error-correction. To simplify the issue, only binary block codes are studied; hence …

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 …

Determination Of Budgetary Expertise Among Public School Library Media Specialists In The State Of Florida, Mary Hosken

CCAC Theses and Dissertations

In 1988, Information Power described skills and duties expected of a school library media specialist. These include familiarity with various forms of educational technology, interpersonal social and communication skills, and proficiency in a wide range of planning and management areas. Simultaneously, restructuring, a movement to site-based management, requires new types of skills of Florida's teachers.

While the importance and complexity of the position of library media specialist has increased, there is concern that some practicing professionals do not have training or experience to address these new obligations. As a benchmark of current expertise in non-instructional duties, this research effort attempted …

A Strategic Plan For Computing And Telecommunications At A University, Dennis J. Huff

CCAC Theses and Dissertations

Embry-Riddle Aeronautical University (ERAU), a multi-campus, four-year institution of higher education specializing in aeronautic and avionic engineering, has recently made a strong commitment to integration of technology into the University environment. Due to a present lack of vision and planning, ERAU secured the services of Technology Specialists, Inc. (TSI) to manage the technology center and develop a five year plan for technology integration. The author was instrumental in the planning and development of the plan. As research has confirmed, technology planning has traditionally been lacking in higher education institutions. The author followed a method for plan development as suggested by …

The Electronic Bulletin Board As A Means Of Professional Communication Among Physics Teachers, Donald L. Mcgarry

CCAC Theses and Dissertations

Teachers of secondary school physics are often physically isolated from their peers; that is, they do not have as much contact with their physics colleagues as they desire. One reason for this physical isolation is the relatively small population of students enrolled in high school physics courses resulting in small numbers of physics teachers per school. Another is that many physics teachers are teaching physics only part time.

One method of communication among teachers has the potential to improve professional communication among physics teachers. This is the computer operated electronic bulletin board system (BBS). Bulletin board systems and variants have …

The Design Of An Effective, Economical Executive Information System For Cedarville College, David L. Rotman

CCAC Theses and Dissertations

The managers of a corporation have an obligation to make the best use of available organizational resources for daily operational activities of the corporation and for long-range development. This requirement for efficient management certainly obtains for higher education, as declining student populations and shrinking funding sources argue for an even greater need to manage well. One important aspect of efficient management is having sufficient information for decision making. This dissertation addresses the need for electronic tools to assist officers of a higher education institution in the management of the institution by improving access to information. College administrators need information about …

Speculative Computation: Overcoming Communication Delays In Parallel Algorithms, Vasudha Govindan, Mark A. Franklin

All Computer Science and Engineering Research

Communication latencies and delays are a major source of performance degradation in parallel computing systems. It is importnat to "mask" these communication delays by overlapping them with useful computation in order to obtain good parallel performance. This paper proposes speculative computation as a technique to mask communication latencies. Speculative computation is discussed in the context of synchronous iterative algorithms. Processors speculate the contents of messages that are not hyet received and perform computation based on the speculated values. When the messages are received, they are compared with the speculated values and, if the error is unacceptable, the resulitng computation is …

Visual Specification Of Interprocess And Intraprocess Communication, T. Paul Mccartney, Kenneth J. Goldman

All Computer Science and Engineering Research

We present a visual specification language for constructing distributed applications and their direct manipulation graphical user interfaces. Each distributed application consists of a collection of independent modules and a configuration of logical connections that define communication among the data interfaces of the modules. Our specification language uses a single visual mechanism that allows end-users to define interprocess communication among distributed modules and to define intraprocess communication among objects within a module. This seamless specification provides a general encapsulation/abstraction mechanism and is designed to support dynamic change to the communication structure. User interfaces are completely decoupled from the module(s) they control.