Digital Commons Network^™

A Library-Based Approach To Task Parallelism In A Data-Parallel Language, Ian Foster, David R. Kohr, Rakesh Krishnaiyer, Alok Choudhary

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

The data-parallel language High Performance Fortran (HPF) does not allow efficient expression of mixed task/data-parallel computations or the coupling of separately compiled data-parallel modules. In this paper, we show how these common parallel program structures can be represented, with only minor extensions to the HPF model, by using a coordination library based on the Message Passing Interface (MPI). This library allows data-parallel tasks to exchange distributed data structures using calls to simple communication functions. We present microbenchmark results that characterize the performance of this library and that quantify the impact of optimizations that allow reuse of communication schedules in common …

A Unified Tiling Approach For Out-Of-Core Computations, Rajesh Bordawekar, Alok Choudhary, J. Ramanujam, Mahmut Kandemir

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

This paper describes a framework by which an out-of-core stencil program written in a data-parallel language can be translated into node programs in a distributed-memory message-passing machine with explicit I/O and communication. We focus on a technique called Data Space Tiling to group data elements into slabs that can fit into memories of processors. Methods to choose legal tile shapes under several constraints and deadlock-free scheduling of tiles are investigated. Our approach is unified in the sense that it can be applied to both FORALL loops and the loops that involve flow-dependences.

Shape Recognition Using Genetic Algorithms, Ender Ozcan, Chilukuri K. Mohan

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

Shape recognition is a challenging task when shapes overlap, forming noisy, occluded, partial shapes. This paper uses a genetic algorithm for matching input shapes with model shapes described in terms of features such as line segments and angles (extracted using traditional algorithms). The quality of matching is gauged using a measure derived from attributed shape grammars [12, 13]. Preliminary results, using shapes with about 30 features each, are extremely encouraging.

Unsupervised Algorithms For Learning Emergent Spatio-Temporal Correlations, Chaitanya Tumuluri

Electrical Engineering and Computer Science - Technical Reports

Many applications require the extraction of spatiotemporal correlations among dynamically emergent features of non-stationary distributions. In such applications it is not possible to obtain an a priori analytical characterization of the emergent distribution. This paper extends the Growing Cell Structures (GCS) network and presents two novel (GIST and GEST) networks, which combine unsupervised feature-extraction and Hebbian learning, for tracking such emergent correlations. The networks were successfully tested on the challenging Data Mapping problem, using an execution driven simulation of their implementation in hardware. The results of the simulations show the successful use of the GIST and GEST networks for extracting …

The Isomorphism Conjecture Fails Relative To A Random Oracle, Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

Electrical Engineering and Computer Science - All Scholarship

Berman and Hartmanis [BH77] conjectured that there is a polynomialtime computable isomorphism between any two languages complete for NP with respect to polynomial-time computable many-one (Karp) reductions. Joseph and Young [JY85] gave a structural definition of a class of NP-complete sets---the k-creative sets---and defined a class of sets (the K k f 's) that are necessarily k-creative. They went on to conjecture that certain of these K k f 's are not isomorphic to the standard NP-complete sets. Clearly, the Berman--Hartmanis and Joseph--Young conjectures cannot both be correct. We introduce a family of strong one-way functions, the scrambling functions. If …

Every Polynomial-Time 1-Degree Collapses Iff P = Pspace, Stephen A. Fenner, Stuart A. Kurtz, James S. Royer

Electrical Engineering and Computer Science - All Scholarship

A set A is m-reducible (or Karp-reducible) to B iff there is a polynomial-time computable function f such that, for all x, x ∈ A <--> f (x) ∈ B. Two sets are: (a) 1-equivalent iff each is m-reducible to the other by one-one reductions; (b) p-invertible equivalent iff each is m-reducible to the other by one-one, polynomial-time invertible reductions; and (c) p-isomorphic iff there is an m-reduction from one set to the other that is one-one, onto, and polynomial-time invertible. In this paper we show the following characterization. Theorem : The following are equivalent: (a) P = PSPACE. (b) Every …

Hierarchical Control Flow Graph Models, Douglas G. Fritz, Robert G. Sargent

Electrical Engineering and Computer Science - All Scholarship

Hierarchical Control Flow Graph Models define a modeling paradigm for discrete event simulation modeling based upon hierarchical extensions to Control Flow Graph Models. Conceptually, models consist of a set of encapsulated, concurrently operating model components that interact solely via message passing. The primary objectives of Hierarchical Control Flow Graph Models are: (1) to facilitate model development by making it easier to develop, maintain, and reuse models and model elements, and (2) to support the flexible and efficient execution of models. Hierarchical Control Flow Graph Models use two complementary types of hierarchical model specification structures, one to specify components and their …

Exploration Of Emerging Hpcn Technologies For Web-Based Distributed Computing, Hon W. Yau, Alvin Leung, Wojtek Furmanski, Geoffrey C. Fox

Northeast Parallel Architecture Center

The surge in the popularity of the World Wide Web (WWW) has corresponded to a decreasing market for specialised high performance computers. This paper discusses how, by making use of technology developed from the broader end of the computing pyramid, much of the past decade's work in distributed computing can be realised in the context of the larger WWW market. Not only do these new technologies offer fresh possibilities, but their pace of development is unlikely to be matched by the traditional high performance research community. A motivating application, discussions of the pertinent emerging technologies, and NPAC's investigations of them, …

Tests Of Random Number Generators Using Ising Model Simulations, Paul D. Coddington

Northeast Parallel Architecture Center

Large-scale Monte Carlo simulations require high-quality random number generators to ensure correct results. The contrapositive of this statement is also true – the quality of random number generators can be tested by using them in large-scale Monte Carlo simulations. We have tested many commonly used random number generators with high precision Monte Carlo simulations of the 2-d Ising model using the Metropolis, Swendsen-Wang, and Wolff algorithms. This work is being extended to the testing of random number generators for parallel computers. The results of these tests are presented, along with recommendations for random number generators for high-performance computers, particularly for …

Neural Computation Of The Eigenvectors Of A Symmetric Positive Definite Matrix, Wenyu Julie Tsai

Theses Digitization Project

No abstract provided.

Array Decompositions For Nonuniform Computational Environments, Maher Kaddoura, Sanjay Ranka, Albert Wang

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

Two-dimensional arrays are useful in a large variety of scientific and engineering applications. Parallelization of these applications requires the decomposition of array elements among different machines. Several data-decomposition techniques have been studied in the literature for machines with uniform computational power. In this paper we develop new methods for decomposing arrays into a cluster of machines with nonuniform computational power. Simulation results show that our methods provide superior decomposition over naive schemes.

Hierarchical Growing Cell Structures, Vanco Burzevski, Chilukuri K. Mohan

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

We propose a hierarchical self-organizing neural network ("HiGS") with adaptive architecture and simple topological organization. This network combines features of Fritzke's Growing Cell Structures and traditional hierarchical clustering algorithms. The height and width of the tree structure depend on the user-specified level of error desired, and the weights in upper layers of the network do not change in later phases of the learning algorithm. Parameters such as node deletion rate are adaptively modified by the learning algorithm.

Cooperative Assistance For Remote Robot Supervision, Robin R. Murphy, Erika Rogers

Computer Science and Software Engineering

This paper describes current work on a cooperative tele-assistance system for semi-autonomous control of mobile 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. It extends recent developments in artificial intelligence in modeling the role of visual interactions in problem solving for application to an interface permitting the human and remote to cooperate in cognitively demanding tasks such as recovering from execution failures, mission planning, and learning. The design of the system is presented, together with a number of exception-handling scenarios …

A Study Of Visual Reasoning In Medical Diagnosis, Erika Rogers

Computer Science and Software Engineering

The purpose of this paper is to describe experimental work conducted in the area of diagnostic radiology,with an emphasis on how perception and problem solving interact in this type of task. This work was part of a larger project whose goals included the development of an information-processing model of visual interaction,and the subsequent design of an intelligent cooperative assistant for this domain.

Verbal protocol data was collected from eight radiologists (six residents and two experts) while they examined seven different computer-displayed chest x-rays. A brief overview of the methodology and analysis techniques is presented, together with specific results from one …

Torus Routing In The Presence Of Multicasts, Hiroki Ishibashi

Theses Digitization Project

No abstract provided.

Optimization Of The Discriminatory Power Of A Trigram Based Document Clustering Algorithm Using Evolutionary Computation, Daniel R. Tauritz

Computer Science Faculty Research & Creative Works

No abstract provided.

Technical-Legal Aspects Of Software Patents, Kenneth Nolan Nichols

Theses Digitization Project

No abstract provided.

Frequency Coordination Between Adjacent Carriers Of Two Cdma Operators, Seung Jong Park, Hun Bum Ha, Jong Tai Chung, Yoon Sub Shim, Do Young Lee

Computer Science Faculty Research & Creative Works

Frequency coordination is the process that assigns frequency bands to neighboring or coexisting systems to minimize interference. This interference is caused by unwanted signals from adjacent frequency bands. Especially, interference is maximized by the spatial near-far problem which occurs in case two different cellular systems serve. This critical case happens when different cellular operators using the adjacent carriers do not collocate their base stations (BS). In this paper, we investigate the frequency coordination when two CDMA operators using adjacent CDMA carriers don't collocate their BS. In order to lessen the unwanted interference, we put the guard band which separates adjacent …

A Systematic Tradeoff Methodology For Acquiring And Validating Imprecise Requirements, J. Yen, Xiaoqing Frank Liu, W. A. Tiao

Computer Science Faculty Research & Creative Works

Requirement analysis is one of the most important phases in a software development process. Existing requirement methodologies are limited in specifying requirements that are usually vague and imprecise, and in supporting tradeoff analysis between the conflicting requirements. In this paper, the elasticity of imprecise requirements is captured using fuzzy logic to facilitate tradeoffs between conflicting requirements. Based on the marginal rate of substitution in decision science, we have developed a systematic approach to elicit the structures and the parameters of imprecise requirements, to validate the scheme for aggregating requirements, and to assess relative priorities of conflicting requirements.

Adaptive Information Filtering As A Means To Overcome Information Overload, Daniel R. Tauritz

Computer Science Faculty Research & Creative Works

Information Filtering is concerned with filtering data streams in such a way as to leave only pertinent data (information) to be perused. When the data streams are produced in a changing environment (as most if not all are) the filtering has to adapt too in order to remain effective. Adaptive Information Filtering (AIF) is concerned with filtering in changing environments. The changes may occur both on the transmission side (the nature of the streams can change), and on the reception side (the interest of a user can change). The thesis research described in this paper combines trigram analysis, clustering, and …

Concepts Of Adaptive Information Filtering, Daniel R. Tauritz

Computer Science Faculty Research & Creative Works

This paper was written for the project study “Adaptive Information Filtering” at the Department of Computer Science, Leiden University, The Netherlands. The assignment was to write an introduction to Adaptive Information Filtering (AIF), based on the author’s ideas for his M.Sc. thesis, and with as large an audience as possible in mind. In addition to a simple introduction to AIF, this paper should also provide easy introductions to clustering algorithms, evolutionary computation, and n-gram analysis. (Preface, page 2)

Syllogism Solving Under Time Pressure, Gondy Leroy, Koen Lamberts

CGU Faculty Publications and Research

No abstract provided.

Semantic And Schematic Similarities Between Database Objects: A Context-Based Approach, Vipul Kashyap, Amit P. Sheth

Kno.e.sis Publications

In a multidatabase system, schematic conflicts between two objects are usually of interest only when the objects have some semantic similarity. We use the concept of semantic proximity, which is essentially an abstraction/mapping between the domains of the two objects associated with the context of comparison. An explicit though partial context representation is proposed and the specificity relationship between contexts is defined. The contexts are organized as a meet semi-lattice and associated operations like the greatest lower bound are defined. The context of comparison and the type of abstractions used to relate the two objects form the basis of a …

Spieltheorie, Alexander Chocholaty, Pascal Hitzler

Computer Science and Engineering Faculty Publications

No abstract provided.

An Examination Of Virtual Reality Modeling Language And Its Implications For The Future Of The World Wide Web, Mitch L. Hamelau

Honors Theses, 1963-2015

This project examines the current and future capabilities of Virtual Reality Modeling Language (VRML). VRML is first looked at in terms of its own current capabilities and limitations and then in terms of the impact that it will have on the World Wide Web. Some examples of future changes to the World Wide Web that may come about due to VRML are examined. Then a specific application is used as an example of the advantages VRML provides for developers who use the World Wide Web.

Using Genetic Algorithms To Solve The Geometric Traveling Salesperson Problem, Michael Criswell

Honors Theses, 1963-2015

Genetic Algorithms use life as their model to solve difficult problems in computer science. They use a collection of possible solutions to find an optimal solution in extremely large search spaces. They follow biological processes such as crossover and mutation and implement Darwinian natural selection to use the better solutions to create more possible solutions until an optimal solution has been found. The Traveling Salesperson Problem lies within a class of problems called NP. These problems are not solvable in a reasonable amount of time using classical methods. Genetic Algorithms are an alternative method for attempting to solve such problems. …

Compile-Time Performance Prediction Of Hpf/Fortran 90d, Manish Parashar, Salim Hariri

Electrical Engineering and Computer Science - All Scholarship

In this paper we present an interpretive approach for accurate and cost-effective performance prediction in a high performance computing environment, and describe the design of a compile-time HPF/Fortran 90D performance prediction framework based on this approach. The performance prediction framework has been implemented as a part of the HPF/Fortran 90D application development environment that integrates it with a HPF/Fortran 90D compiler and a functional interpreter. The current implementation of the environment framework is targeted to the iPSC/860 hypercube multicomputer system. A set of benchmarking kernels and application codes have been used to validate the accuracy, utility, and usability of the …

Snap, Crackle, Webwindows!, Geoffrey C. Fox, Wojtek Furmanski

Northeast Parallel Architecture Center

We elaborate the SNAP---Scalable (ATM) Network and (PC) Platforms---view of computing in the year 2000. The World Wide Web will continue its rapid evolution, and in the future, applications will not be written for Windows NT/95 or UNIX, but rather for WebWindows with interfaces defined by the standards of Web servers and clients. This universal environment will support WebTop productivity tools, such as WebWord, WebLotus123, and WebNotes built in modular dynamic fashion, and undermining the business model for large software companies. We define a layered WebWindows software architecture in which applications are built on top of multi-use services. We discuss …

Rex ' 96 : An Expert Guide To Revegetation, David Bicknell

Journal of the Department of Agriculture, Western Australia, Series 4

Agriculture Western Australia has provided coordination and technical input to a powerful source of information on plants for Australian conditions. David Bicknell outlines some of its features and uses.

Farmers, local government, advisers and even gardeners often have trouble finding the right plant for the right place for a given purpose. Rather than spend a lot of time, money and effort looking through scattered sources of information, many people stick with a limited number of species year after year. This neglects plants that may be much better suited to the purpose, and also fails to develop Australia's huge range of …

Towards A Model For Software Project Estimating, Stuart Hope

Theses : Honours

The use and development of software is an integral and critical part of modern industrial society. The outcomes of many software development and maintenance projects have been less than satisfactory with significant numbers being over schedule, lacking in functionality and over budget. These problems are the result of poor management of both the process and the product. One of the major problems to overcome in the management of software development projects is the ability to predict the outcomes early in the project when there are a large number of unknowns. The ability to reliably predict the outcomes in a repeatable …