Digital Commons Network^™

A High Level Spmd Programming Model: Hpspmd And Its Java Language Binding, Guansong Zhang, Bryan Carpenter, Geoffrey C. Fox, Xinying Li

Northeast Parallel Architecture Center

This report introduces a new language, HPJava, for parallel programming on message passing systems. The language provides a high level SPMD programming model. Through examples and performance results, the features of the new programming style, and its implementation, are illustrated.

The Impact Of Technology On Special Education Students, Nathaniel T. Schutta

Honors Theses, 1963-2015

Computers are becoming a part of our everyday life. Every facet of our society, including education, is changing in response. This thesis asks: what impact is technology having on students in one special education classroom? This thesis gives an overview of what technology is present in classrooms, how technology has been used, and examines the handful of studies that have been conducted on the impact of technology on students. I examined a special education classroom focused on the use and maintenance of computers, use of the Internet, and the use of multimedia for presentations. A study was conducted that investigated …

Parallel Probabilistic Computations On A Cluster Of Workstations, Atanas Radenski, Andrew Vann, Boyana Norris

Mathematics, Physics, and Computer Science Faculty Books and Book Chapters

Probabilistic algorithms are computationally intensive approximate methods for solving intractable problems. Probabilistic algorithms are excellent candidates for cluster computations because they require little communication and synchronization. It is possible to specify a common parallel control structure as a generic algorithm for probabilistic cluster computations. Such a generic parallel algorithm can be glued together with domain-specific sequential algorithms in order to derive approximate parallel solutions for different intractable problems.

In this paper we propose a generic algorithm for probabilistic computations on a cluster of workstations. We use this generic algorithm to derive specific parallel algorithms for two discrete optimization problems: the …

Systolic Algorithm For Processing Rle Images, Hao Feng, Fikret Erçal, Filiz Bunyak

Computer Science Faculty Research & Creative Works

Image difference operation is commonly used in on-line automated printed circuit board (PCB) inspection systems as well as many other image processing applications. In this paper, we describe a new systolic algorithm and its system architecture which computes image differences in run-length encoded (RLE) format. The efficiency of this operation greatly affects the overall performance of the inspection system. It is shown that, for images with a high similarity measure, the time complexity of the systolic algorithm is a small constant. A formal proof of correctness for the algorithm is also given in the paper.

Design And Design Centers In Engineering Education, Clive L. Dym

All HMC Faculty Publications and Research

This paper is intended to be the opening salvo of the workshop, Computing Futures in Engineering Design (Dym, 1997). Thus, I want to take this privileged moment to ask you to think with me about the role of design in engineering. In particular, I want to reflect upon how design is articulated and how design is taught; about the role of design in engineering education and in the practice of engineering; and about the role that could be played locally and, perhaps, nationally by a center devoted to design education. Because I teach here at Harvey Mudd College (HMC), …

Design, Implementation, And Evaluation Of Parallell Pipelined Stap On Parallel Computers, Alok Choudhary, Wei-Keng Liao, Donald Weiner, Pramod Varshney, Richard Linderman, Mark Linderman

Electrical Engineering and Computer Science - All Scholarship

Performance results are presented for the design and implementation of parallel pipelined space-time adaptive processing (STAP) algorithms on parallel computers. In particular, the issues involved in parallelization, our approach to parallelization, and performance results on an Intel Paragon are described. The process of developing software for such an application on parallel computers when latency and throughput are both considered together is discussed and tradeoffs considered with respect to inter and intratask communication and data redistribution are presented. The results show that not only scalable performance was achieved for individual component tasks of STAP but linear speedups were obtained for the …

A Multithreaded Message-Passing System For High Performance Distributed Computing Applications, Sung-Yong Park, Joohan Lee, Salim Hariri

Electrical Engineering and Computer Science - All Scholarship

High Performance Distributed Computing (HPDC) applications require low-latency and high-throughput communication services and HPDC applications have different Quality of Service (QOS) requirements (e.g., bandwidth requirement, flow/error control algorithms, etc.). The communication services provided by traditional message-passing systems are fixed and thus can not be changed to meet the requirements of different HPDC applications. NYNET (ATM wide area network testbed in New York state) Communication System (NCS) is a multithreaded message-passing system developed at Syracuse University that provides high-performance and flexible communication services. In this paper, we overview the general architecture of NCS and present how NCS communication services are implemented. …

A Problem Solving Environment For Network Computing, Salim Hariri, Haluk Topcuoglu, Wojtek Furmanski, Dongmin Kim, Yoonhee Kim

Electrical Engineering and Computer Science - All Scholarship

The current advances in high-speed networks and WWW technologies have made network computing a cost-effective high performance computing environment. New software development models and problem solving environments must be developed to utilize the network computing environment efficiently. In this paper we present Virtual Distributed Computing Environment (VDCE), which provides a problem solving environment for high-performance distributed computing over wide-area networks. VDCE enables scientists to develop distributed applications without knowing the detailed architecture of the underlying resources. VDCE provides well-defined library functions that relieve end users from tedious task implementations and it supports software reusability. The VDCE software architecture consists of …

Automatic Granularity Control For Load Balancing Of Concurrent Particle Simulations, Marc Rieffel, Stephen Taylor, Jerrell Watts

Electrical Engineering and Computer Science - All Scholarship

This paper demonstrates the use of automatic granularity control as part of dynamic load balancing for irregular, particle-based simulations. Performance optimization techniques are considered in the context of a concurrent Direct Simulation Monte Carlo method used to study the rarefied gas flow inside three-dimensional plasma reactors. Several computational techniques are used to reduce the overall time to deliver realistic threedimensional results. The effectiveness of dynamic load balancing and granularity control are presented for large-scale simulations on distributed-memory multicomputers.

Performance Enhancement Using Intra-Server Caching In A Continuous Media Server, Chutimet Srinilta, Alok Choudhary

Electrical Engineering and Computer Science - All Scholarship

Continuity of stream playback is the crucial constraint in designing a continuous media server. From a distributed memory architectural model developed earlier, we found that there were many points where the stream capacity of the server could be improved. The stream capacity was usually limited by the storage bottlenecks. Serving streams from memory cache eliminates disk accesses and data transfers between nodes which, in turn, helps relieve those bottlenecks. However, the capacity of the server ultimately depends on client access pattern. Client request assignment has an impact on cache hit ratio as well as workload distribution. It is also the …

Verification And Validation Of Simulation Models, Robert G. Sargent

Electrical Engineering and Computer Science - All Scholarship

This paper discusses verification and validation of simulation models. The different approaches to deciding model validity are presented; how model verification and validation relate to the model development process are discussed; various validation techniques are defined; conceptual model validity, model verification, operational validity, and data validity are described; ways to document results are given; and a recommended procedure is presented.

Ai And The Changing Face Of Health Care, Erika Rogers

Computer Science and Software Engineering

No abstract provided.

Interactive Image Cases For Medical Problem Solving, Erika Rogers, Barb Ericson

Computer Science and Software Engineering

The development of an intelligent assistance agent for diagnostic radiology faces a number of challenges: e.g., how to gain access to the knowledge used an such visual problem solving tasks, how to operationalize it for further processing, and how to present it an the most useful manner for diagnosis. Our previous work an this domain placed an emphasis on the first two issues, and has shown that both perception and problem solving need to be supported an these types of tasks. However, the interface to the underlying intelligence in our first prototypes did not reflect how medical practitioners physically interact …

Segmentation Of Printed Circuit Board Images Into Basic Patterns, Madhav Moganti, Fikret Ercal

Computer Science Faculty Research & Creative Works

Segmentation is the first and foremost step in the inspection of the printed circuit boards. In this paper a new technique for the segmentation of printed circuit board (PCB) images is presented. The technique basically segments a given PCB into small windows containing primitive PCB subpatterns. The technique proposed exploits the simplicity and the homogeneity of the PCB images and is inherently parallel. A detailed discussion of the experiments and the results obtained is also presented. © 1993 Academic Press.

Optimal Contention-Free Unicast-Based Multicasting In Switch-Based Networks Of Workstations, Ran Libeskind-Hadas, Dominic Mazzoni '99, Ranjith Rajagopalan '99

All HMC Faculty Publications and Research

A unicast-based multicasting algorithm is presented for arbitrary interconnection networks arising in switch-based networks of workstations. The algorithm is optimal with respect tot he number of startups incurred and is provably free from depth contention. Specifically, no two constituent unicasts for the same multicast contend for a common channel, even if some unicasts are delayed due to unpredictable variations in latencies. The algorithm uses an underlying partially adaptive deadlock-free unicast routing algorithm. Simulation results indicate that the algorithm behaves as predicted by its theoretical properties and provides a promising approach to unicast-based multicasting.

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 14, Number 1, January 1998, 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.

The Simple Genetic Algorithm And The Walsh Transform: Part Ii, The Inverse, Michael D. Vose, Alden H. Wright

Computer Science Faculty Publications

This paper continues the development, begun in Part I, of the relationship between the simple genetic algorithm and the Walsh transform. The mixing scheme (comprised of crossover and mutation) is essentially “triangularized” when expressed in terms of the Walsh basis. This leads to a formulation of the inverse of the expected next generation operator. The fixed points of the mixing scheme are also determined, and a formula is obtained giving the fixed point corresponding to any starting population. Geiringer's theorem follows from these results in the special case corresponding to zero mutation.

The Simple Genetic Algorithm And The Walsh Transform: Part I: Theory, Michael D. Vose, Alden H. Wright

Computer Science Faculty Publications

This paper is the first part of a two-part series. It proves a number of direct relationships between the Fourier transform and the simple genetic algorithm. (For a binary representation, the Walsh transform is the Fourier transform.) The results are of a theoretical nature and are based on the analysis of mutation and crossover. The Fourier transform of the mixing matrix is shown to be sparse. An explicit formula is given for the spectrum of the differential of the mixing transformation. By using the Fourier representation and the fast Fourier transform, one generation of the infinite population simple genetic algorithm …

Data Mining In Electronic Media Usage Statistics: A Case Study Of Knowledge Discovery In Databases, Peter J. Lindquist

Honors Theses, 1963-2015

As databases grow larger, analysts are turning to computers to help them analyze the massive amounts of data their computers have collected. As the difference between having data and having useful information becomes more clear, different methods of using computers to analyze data are becoming available. Knowledge Discovery in Databases (KDD) is a general methodology for preparing the data, using software algorithms to discover new patterns or relationships in the data, and integrating the results back into the system. The KDD methodology is explained and hypothetically applied to usage statistics generated by the CSB/SJU Libraries Internet resources. Examples are drawn …

Heraldry And Programming Languages: The Complexity Of Natural Languages Examined Through The Parsing Of The Heraldic Blazon, Hans A. Mersinger

Honors Theses, 1963-2015

The idea of programming computers to understand human speech and written text has been the dream, even the Holy Grail, of computer scientists and many others, since before the first computers where created. Computers in countless movies and television shows have been able to understand, and therefore interact with, the humans around them but until recently this possibility has been pure science fiction. By studying, and then attempting, the methods of parsing the heraldic language, one hopes to show some of the methods that are used to remove the ambiguity in natural languages that hamper their parsing. Given time, I …

Skew-Insensitive Parallel Algorithms For Relational Join, Khaled Alsabti, Sanjay Ranka

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

Join is the most important and expensive operation in relational databases. The parallel join operation is very sensitive to the presence of the data skew. In this paper, we present two new parallel join algorithms for coarse grained machines which work optimally in presence of arbitrary amount of data skew. The first algorithm is sort-based and the second is hash-based. Both of these algorithms employ a preprocessing phase (prior to the redistribution phase) to equally partition the work among the processors. The proposed algorithms have been designed for memory resident-data. However, they can be extended to disk resident-data. These algorithms …

The Design And Evaluation Of A Virtual Distributed Computing Environment, Haluk Topcuoglu, Salim Hariri, Dongmin Kim, Yoonhee Kim, Xue Bing

Electrical Engineering and Computer Science - All Scholarship

In this paper we present the Virtual Distributed Computing Environment (VDCE), a metacomputing environment currently being developed at Syracuse University. VDCE provides an efficient web-based approach for developing, evaluating and visualizing large-scale distributed applications that are based on predefined task libraries on diverse platforms. The VDCE task libraries relieve end-users of tedious task implementations and also support reusability. The VDCE software architecture is described in terms of three modules: a) the Application Editor, a user-friendly application development environment that generates the Application Flow Graph (AFG) of an application; b) the Application Scheduler, which provides an efficient task-to-resource mapping of AFG; …

Adaptive Linkage Crossover, Ayed A. Salman, Kishan Mehrotra, Chilukuri K. Mohan

Electrical Engineering and Computer Science - All Scholarship

Problem-specific knowledge is often implemented in search algorithms using heuristics to determine which search paths are to be explored at any given instant. As in other search methods, utilizing this knowledge will more quickly lead a genetic algorithm (GA) towards better results. In many problems, crucial knowledge is not found in individual components, but in the interrelations between those components. For such problems, we develop an interrelation (linkage) based crossover operator that has the advantage of liberating GAs from the constraints imposed by the fixed representations generally chosen for problems. The strength of linkages between components of a chromosomal structure …

Adaptive Prefetching For Device-Independent File I/O, Dan Revel, Dylan Mcnamee, David Steere, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Device independent I/O has been a holy grail to operating system designers since the early days of UNIX. Unfortunately, existing operating systems fall short of this goal for multimedia applications. Techniques such as caching and sequential read-ahead can help mask I/O latency in some cases, but in others they increase latency and add substantial jitter. Multimedia applications, such as video players, are sensitive to vagaries in performance since I/O latency and jitter affect the quality of presentation. Our solution uses adaptive prefetching to reduce both latency and jitter. Applications submit file access plans to the prefetcher, which then generates I/O …

Stackguard: Automatic Adaptive Detection And Prevention Of Buffer-Overflow Attacks, Crispin Cowan, Calton Pu, David Maier, Heather Hinton, Jonathan Walpole, Peat Bakke, Steve Beattie, Aaron Grier, Perry Wagle, Qian Zhang

Computer Science Faculty Publications and Presentations

This paper presents a systematic solution to the persistent problem of buffer overflow attacks. Buffer overflow attacks gained notoriety in 1988 as part of the Morris Worm incident on the Internet. While it is fairly simple to fix individual buffer overflow vulnerabilities, buffer overflow attacks continue to this day. Hundreds of attacks have been discovered, and while most of the obvious vulnerabilities have now been patched, more sophisticated buffer overflow attacks continue to emerge.

We describe StackGuard: a simple compiler technique that virtually eliminates buffer overflow vulnerabilities with only modest performance penalties. Privileged programs that are recompiled with the StackGuard …

A Complex-Systems Perspective On The “Computation Vs. Dynamics” Debate In Cognitive Science, Melanie Mitchell

Computer Science Faculty Publications and Presentations

I review the purported opposition between computational and dynamical approaches in cognitive science. I argue that both computational and dynamical notions will be necessary for a full explanatory account of cognition, and give a perspective on how recent research in complex systems can lead to a much needed rapprochement between computational and dynamical styles of explanation.

Statistical Dynamics Of The Royal Road Genetic Algorithm, Erik Van Nimwegen, James P. Crutchfield, Melanie Mitchell

Computer Science Faculty Publications and Presentations

Metastability is a common phenomenon. Many evolutionary processes, both natural and artificial, alternate between periods of stasis and brief periods of rapid change in their behavior. In this paper an analytical model for the dynamics of a mutation-only genetic algorithm (GA) is introduced that identifies a new and general mechanism causing metastability in evolutionary dynamics. The GA’s population dynamics is described in terms of flows in the space of fitness distributions. The trajectories through fitness distribution space are derived in closed form in the limit of infinite populations. We then show how finite populations induce metastability, even in regions where …

Generalized Ultrametrics, Domains And An Application To Computational Logic, Anthony K. Seda, Pascal Hitzler

Computer Science and Engineering Faculty Publications

Fixed points of functions and operators are of fundamental importance in programming language semantics in giving meaning to recursive definitions and to constructs which involve self-reference. It follows therefore that fixed-point theorems are also of fundamental importance in theoretical computer science. Often, order-theoretic arguments are available in which case the well-known Knaster-Tarski theorem can be used to obtain fixed-points. Sometimes, however, analytical arguments are needed involving the Banach contraction mapping theorem as is the case for example in studying concurrency and communicating systems. Situations arise also in computational logic in the presence of negation which force non-monotonicity of the operators …

Jworb - Java Web Object Request Broker For Commodity Software Based Visual Data Ow Metacomputing Programming Environment, Geoffrey C. Fox, Wojtek Furmanski, Hasan T. Ozdemir

Northeast Parallel Architecture Center

Programming environments and tools that are simultaneously sustainable, highly functional, robust and easy to use have been hard to come by in the HPDC area. This is partially due to the difficulty in developing sophisticated customized systems for what is relatively small part of the worldwide computing enterprise. As the commodity software becomes naturally distributed with the onset of Web and Intranets, we observe now a new trend in HPDC community [1, 8, 12] to base high performance computing on the modern enterprise computing technologies. .. JWORB is a multi-protocol Java server under development at NPAC, currently capable of handling …

Robots In The Undergraduate Curriculum, D. Kumar, Lisa A. Meeden

Computer Science Faculty Works

No abstract provided.