Digital Commons Network^™

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 …

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.

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

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 …

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.

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 …

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.

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 …

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.

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 …

High-Performance Training Of Feedforward & Simple Recurrent Networks, Barry L. Kalman, Stan C. Kwasny

All Computer Science and Engineering Research

TRAINREC is a system for training feedforward and recurrent neural networks that incorporates several ideas. It uses the conjugate-gradient method which is demonstrably more efficient than traditional backward error propagation. We assume epoch-based training and derive a new error function having several desirable properties absent from the traditional sum-of-squared-error function. We argue for skip (shortcut) connections where appropriate and the preference for a sigmoidal yielding values over the [-1,1] interval. The input feature space is often over-analyzed, but by using singular value decomposition, input patterns can be conditioned for better learning often with a reduced number of input units. Recurrent …

Cell Tracking Using A Distributed Algorithm For 3d Image Segmentation, Vikas Awasthi, Keith W. Doolittle, Guru Parulkar, James G. Mcnally

All Computer Science and Engineering Research

We have developed and tested an automated method for simultaneous 3D tracking of numerous, flourescently-tagged cells. The procedure uses multiple thresholding to segment individual cells at a starting timepoint, and then iteratively applies a template-matching algorithm to locate a particular cell's position at subsequent time points. To speed up the method, we have developed a distributed implementation in which template matching is carried out in parallel on several different server machines. The distributed implementation showed a monotonic decrease in response time with increasing number of servers (up to 15 tested), demonstrating that the tracking algorithm is well suited to parallelization, …

Design Of An Application Development Toolkit For Hpf/Fortran 90d, Manish Parashar, Salim Hariri, Tomasz Haupt, Geoffrey C. Fox

Northeast Parallel Architecture Center

The development of efficient application software capable of exploiting available High Performance Computing (HPC) systems is non-trivial and is largely governed by the availability of sufficiently high-level languages, tools, and application development environments. In this paper we describe the design and operation of a toolkit for HPF/Fortran 90D application development. The toolkit incorporates the following systems: (1) ESP: An Interpretive Framework for HPF/Fortran 90D Performance Prediction; (2) ESP-i: A HPF/Fortran 90D Functional Interpreter; and (3) ESPial: An Integrated Environment for HPF/Fortran 90D Application Development & Execution. The toolkit has been implemented on the iPSC/860 hypercube system, and is supported by …

Interpreting The Performance Of Hpf/Fortran 90d, Manish Parashar, Salim Hariri, Tomasz Haupt, Geoffrey C. Fox

Northeast Parallel Architecture Center

In this paper we present a novel interpretive approach for accurate and cost-effective performance prediction in a high performance computing environment, and describe the design of a source-driven HPF/Fortran 90D performance prediction framework based on this approach. The performance prediction framework has been implemented as part of a HPF/Fortran 90D application development environment. A set of benchmarking kernels and application codes are used to validate the accuracy, utility, usability, and cost-effectiveness of the performance prediction framework. The use of the framework for selecting appropriate compiler directives and for application performance debugging is demonstrated. Keywords: Performance prediction, HPF/Fortran 90D application development, …

Run-Time And Compile-Time Support For Adaptive Irregular Problems, Shamik D. Sharma, Ravi Ponnusamy, Bongki Moon, Yuan-Shin Hwang

Northeast Parallel Architecture Center

In adaptive irregular problems the data arrays are accessed via indirection arrays, and data access patterns change during computation. Implementing such problems on distributed memory machines requires support for dynamic data partitioning, efficient preprocessing and fast data migration. This research presents efficient runtime primitives for such problems. This new set of primitives is part of the CHAOS library. It subsumes the previous PARTI library which targeted only static irregular problems. To demonstrate the efficacy of the runtime support, two real adaptive irregular applications have been parallelized using CHAOS primitives: a molecular dynamics code (CHARMM) and a particle-in-cell code (DSMC). The …

Compiling Fortran 90d/Hpf For Distributed Memory Mimd Computers, Zeki Bozkus, Alok Choudhary, Geoffrey C. Fox, Tomasz Haupt

Northeast Parallel Architecture Center

This paper describes the design of the Fortran90D/HPF compiler, a source-to-source parallel compiler for distributed memory systems being developed at Syracuse University. Fortran 90D/HPF is a data parallel language with special directives to specify data alignment and distributions. A systematic methodology to process distribution directives of Fortran 90D/HPF is presented. Furthermore, techniques for data and computation partitioning, communication detection and generation, and the run-time support for the compiler are discussed. Finally, initial performance results for the compiler are presented. We believe that the methodology to process data distribution, computation partitioning, communication system design and the overall compiler design can be …

Analysis Of Random Number Generators Using Monte Carlo Simulation, Paul D. Coddington

Northeast Parallel Architecture Center

Monte Carlo simulation is one of the main applications involving the use of random number generators. It is also one of the best methods of testing the randomness properties of such generators, by comparing results of simulations using different generators with each other, or with analytic results. Here we compare the performance of some popular random number generators by high precision Monte Carlo simulation of the 2-d Ising model, for which exact results are known, using the Metropolis, Swendsen-Wang, and Wolff Monte Carlo algorithms. Many widely used generators that perform well in standard statistical tests are shown to fail these …

The Design And Evolution Of Zipcode, Anthony Skjellum, Steven G. Smith, Nathan E. Doss, Alvin Leung

Northeast Parallel Architecture Center

Zipcode is a message-passing and process-management system that was designed for multicomputers and homogeneous networks of computers in order to support libraries and large-scale multicomputer software. The system has evolved significantly over the last five years, based on our experiences and identified needs. Features of Zipcode that were originally unique to it, were its simultaneous support of static process groups, communication contexts, and virtual topologies, forming the "mailer" data structure. Point-to-point and collective operations reference the underlying group, and use contexts to avoid mixing up messages. Recently, we have added "gather-send" and "receive-scatter" semantics, based on persistent Zipcode "invoices," both …

A Communication System For High-Performance Distributed Computing, Salim Hariri, Jongbaek Park, Manish Parashar, Geoffrey C. Fox

Northeast Parallel Architecture Center

With the current advances in computer and networking technology coupled with the availability of software tools for parallel and distributed computing, there has been increased interests in high-performance distributed computing (HPDC). We envision that HPDC environments with supercomputing capabilities will be available in the near future. However, a number of issues have to be resolved before future network-based applications can exploit fully the potential of HPDC environment. In this paper, we present an architecture of a high-speed local area network and a communication system that provides HPDC applications with high bandwidth and low latency. We also characterize the message-passing primitives …

Involvement Of Industry In The National High Performance Computing And Communication Enterprise, Geoffrey C. Fox

Northeast Parallel Architecture Center

We discuss aspects of a national computer science agenda for High Performance Computing and Communications (HPCC). We agree with the general direction and emphasis of the current program. In particular, the strong experimental component and linkage of applications with computer science should be continued. We recommend accelerating the emphasis on "national challenges " with more applications and technologies from the information, as compared to simulation areas. We suggest modifying the grand challenge concept to complement the current teaming of particular computer science and applications researchers. We would emphasize better linking of each application group to the entire (inter) national computer …

A Study Of Software Development For High Performance Computing, Manish Parashar, Salim Hariri, Tomasz Haupt, Geoffrey C. Fox

Northeast Parallel Architecture Center

Software development in a High Performance Computing (HPC) environment is non-trivial and requires a thorough understanding of the application and the architecture. The objective of this paper is to study the software development process in a high performance computing environment and to outline the stages typically encountered in this process. Support required at each stage is also highlighted. The modeling of stock option pricing is used as a running example in the study.

Developing Modular Application Builders To Exploit Mimd Parallel Resources, C. Thornborrow, C. Faigle

Northeast Parallel Architecture Center

Modular application builders (MABs), such as AVS and Iris Explorer[6, 7] are increasingly being used in the visualisation community. Such systems can already place compute intensive modules on supercomputers in order to utilise their power. This paper details two major projects at EPCC which attempted to fully integrate the MAB concept with a distributed memory MIMD (DM-MIMD) environment. The work presented was driven by two goals, efficient use of the resource and ease of use by programmer and end user. We present a model of MABs and describe the major problems faced, giving solutions to them through two case studies.

The Virtual Computing Environment, Philip Rousselle, Paul Tymann, Salim Hariri, Geoffrey C. Fox

Northeast Parallel Architecture Center

A network of supercomputers and high-performance workstations appears to be the only reasonable way to provide adequate computing resources for the Grand Challenge problems of the next century. Such a collection of computers and supporting software environments is called a virtual computing environment (VCE). This paper describes the motivation and goals of the VCE project, followed by a description of the system. The paper concentrates on the runtime aspects of the VCE, and concludes with a discussion of a small prototype system that has been built using the Isis distributed toolkit.

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 …

Translation Of Semantic Aspects Of Oodini Graphical Representation To Onto Oodb Data Definition Language, Xiaoyong Wang

Theses

In this thesis we present a system to translate the semantic elements in the graphical schema language of OODINI from API of OODAL to the Type definition of ONTOS DB. To translate semantic constraints of the graphical language, we patch more information to existent class data structure in API of OODAL. After a brief review of OODINI, ONTOS DB and the existent translator without the ability to translate semantic constraints, we describe in detail the methods to translate the essential relationship. dependent relationship, multi-valued essential relationship and multi-valued dependent relationship. We employ an Inverse Reference to a "Set of" Type …

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.

Skin Cancer Diagnosis Using Hierarchical Neural Networks And Fuzzy Logic, Hsi-Chieh Lee

Masters Theses

"Skin cancer, the most common cancer in the United States that affects about 600,000 Americans every year, accounts for 1 % of all cancer deaths. Among all, Malignant Melanoma is the most virulent form of skin cancer that is responsible for 75% of all deaths from skin cancer. In 1992, approximately 32,000 people are expected to develop melanoma and about 6,700 will die. However, even malignant melanoma can be treated successfully if detected in the early phase. Therefore, our research goal is to diagnose skin cancer, especially malignant melanoma.

In this study, only the digitized images obtained from color tumor …

Issues And Obstacles With Multimedia Authoring, Fillia Makedon, Samuel A. Rebelsky, Matthew Cheyney, Charles Owen, Peter Gloor

Dartmouth Scholarship

Unlike traditional authoring, multimedia authoring involves making hard choices, forecasting technological evolution and adapting to software and hardware technology changes. It is, perhaps, an unstable field of endeavor for an academic to be in. Yet, it is important that academics are, in fact, part of this process. This paper discusses some of the common threads shared by three dissimilar cases of multimedia authoring which we have experimented with, that of multimedia conference proceedings, multimedia courseware development and multimedia information kiosks. We consider these applications from an academic point of view and review the benefits and pitfalls of academic development while …