Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons

Open Access. Powered by Scholars. Published by Universities.®

Computer Sciences

Institution
Keyword
Publication Year
Publication
Publication Type
File Type

Articles 54181 - 54210 of 57999

Full-Text Articles in Physical Sciences and Mathematics

Behavior-Based Analogy-Making, Doug Blank Jan 1996

Behavior-Based Analogy-Making, Doug Blank

Computer Science Faculty Research and Scholarship

No abstract provided.


Analogy-Making: A Connectionist Exploration, Doug Blank Jan 1996

Analogy-Making: A Connectionist Exploration, Doug Blank

Computer Science Faculty Research and Scholarship

No abstract provided.


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

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 …


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

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 Jan 1996

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.


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

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 Jan 1996

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 Jan 1996

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 …


Benchmarking The Computation And Communication Performance Of The Cm-5, Kivanc Dincer, Zeki Bozkus, Sanjay Ranka, Geoffrey C. Fox Jan 1996

Benchmarking The Computation And Communication Performance Of The Cm-5, Kivanc Dincer, Zeki Bozkus, Sanjay Ranka, Geoffrey C. Fox

Northeast Parallel Architecture Center

Thinking Machines' CM-5 machine is a distributed-memory, message-passing computer. In this paper we devise a performance benchmark for the base and vector units and the data communication networks of the CM-5 machine. We model the communication characteristics such as communication latency and bandwidths of point-to-point and global communication primitives. We show, on a simple Gaussian elimination code, that an accurate static performance estimation of parallel algorithms is possible by using those basic machine properties connected with computation, vectorization, communication, and synchronization. Furthermore, we describe the embedding of meshes or hypercubes on the CM-5 fat-tree topology and illustrate the performance results …


An Extended Two-Phase Method For Accessing Sections Of Out-Of-Core Arrays, Rajeev Thakur, Alok Choudhary Jan 1996

An Extended Two-Phase Method For Accessing Sections Of Out-Of-Core Arrays, Rajeev Thakur, Alok Choudhary

Electrical Engineering and Computer Science - All Scholarship

A number of applications on parallel computers deal with very large data sets that cannot fit in the main memory. In such applications, data must be stored in files on disks and fetched into memory during program execution. Parallel programs with large out-of-core arrays stored in files must read/write smaller sections of the arrays from/to files. In this paper, we describe a method for accessing sections of out-of-core arrays efficiently. Our method, the extended two phase method, uses collective I/O: Processors cooperate to combine several I/O requests into fewer larger granularity requests, reorder requests so that the file is accessed …


Efficient Algorithms For Array Redistribution, Rajeev Thakur, Alok Choudhary, J. Ramanujam Jan 1996

Efficient Algorithms For Array Redistribution, Rajeev Thakur, Alok Choudhary, J. Ramanujam

Electrical Engineering and Computer Science - All Scholarship

Dynamic redistribution of arrays is required very often in programs on distributed memory parallel computers. This paper presents efficient algorithms for redistribution between different cyclic(k) distributions, as defined in High Performance Fortran. We first propose special optimized algorithms for a cyclic(x) to cyclic(y) redistribution when x is a multiple of y, or y is a multiple of x. We then propose two algorithms, called the GCD method and the LCM method, for the general cyclic(x) to cyclic(y) redistribution when there is no particular relation between x and y. We have implemented these algorithms on the Intel Touchstone Delta, and find …


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

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 Jan 1996

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 …


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

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 …


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

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 …


Spieltheorie, Alexander Chocholaty, Pascal Hitzler Jan 1996

Spieltheorie, Alexander Chocholaty, Pascal Hitzler

Computer Science and Engineering Faculty Publications

No abstract provided.


Compositional Reasoning Is Not Possible In Determining The Solvability Of Consensus, Prasad Jayanti Jan 1996

Compositional Reasoning Is Not Possible In Determining The Solvability Of Consensus, Prasad Jayanti

Computer Science Technical Reports

Consensus, which requires processes with different input values to eventually agree on one of these values, is a fundamental problem in fault-tolerant computing. We study this problem in the context of asynchronous shared-memory systems. In our model, shared-memory consists of a sequence of cells and supports a specific set of operations. Prior research on consensus focussed on its solvability in shared-memories supporting specific operations. In this paper, we investigate the following general question: Let OP1 and OP2 be any two sets of operations such that each set includes read and write operations. Suppose there is no consensus protocol for N …


Optimal Solution Of Off-Line And On-Line Generalized Caching, Saied Hosseini-Khayat, Jerome R. Cox Jan 1996

Optimal Solution Of Off-Line And On-Line Generalized Caching, Saied Hosseini-Khayat, Jerome R. Cox

All Computer Science and Engineering Research

Network traffic can be reduced significantly if caching is utilized effectively. As an effort in this direction we study the replacement problem that arises in caching of multimedia objects. The size of objects and the cost of cache misses are assumed non-uniform. The non-uniformity of size is inherent in multimedia objects, and the non-uniformity of cost is due to the non-uniformity of size and the fact that the objects are scattered throughout the network. Although a special case of this problem, i.e. the case of uniform size and cost, has been extensively studied, the general case needs a great deal …


End-User Construction And Configuration Of Distributed Multimedia Applications, Terrance Paul Mccartney Jan 1996

End-User Construction And Configuration Of Distributed Multimedia Applications, Terrance Paul Mccartney

All Computer Science and Engineering Research

Distributed multimedia applications supported by a global electronic infrastructure have tremendous potential for providing users with customized communication and computation environments. Since communication and computation requirements vary by context and change dynamically, it is unlikely that off-the-shelf applications will anticipate the needs of all users. Therefore, empowering end-users to create their own customized applications for both communication and computation is an important challenge. This dissertation presents several mechanisms that enable end-users to create and configure distributed multimedia applications, including end-users construction direct manipulation graphical users interface (GUIs) and application management of distributed multimedia applications over the Internet.


Global Telerobotics: Exploring Effective Internet Access To Robots, Simon Hartfiel, Susan Hartfiel, Leone Dunn Jan 1996

Global Telerobotics: Exploring Effective Internet Access To Robots, Simon Hartfiel, Susan Hartfiel, Leone Dunn

Faculty of Informatics - Papers (Archive)

This paper describes an Industrial Automation research project at the University of Wollongong, Australia. The project aims to develop a telerobotic planning and control architecture and human robot interface that can be used for intervention robots which require task level programming. In order to investigate global telerobotic principles, the workspace will be made accessible across the Internet via the World Wide Web. The paper describes the experimental setup and implementation of this project, focussing on a discussion of human robot interaction issues, such as interface design problems and the use of a World Wide Web browser for user interaction.


Web Intelligent Query - Disconnected Web Browsing Using Cooperative Techniques, Ramanathan Kavasseri, Todd Keating, Michael Wittman, Anupam Joshi, Sanjiva Weerawarana Jan 1996

Web Intelligent Query - Disconnected Web Browsing Using Cooperative Techniques, Ramanathan Kavasseri, Todd Keating, Michael Wittman, Anupam Joshi, Sanjiva Weerawarana

Department of Computer Science Technical Reports

No abstract provided.


Scalable Scientific Software Libraries And Problem Solving Environments, John R. Rice Jan 1996

Scalable Scientific Software Libraries And Problem Solving Environments, John R. Rice

Department of Computer Science Technical Reports

No abstract provided.


A Survey Of Mobile Transaction Models, Abdelsalam Helal, Santosh Balakrishnan, Margaret Dunham, Ramez Elmasri Jan 1996

A Survey Of Mobile Transaction Models, Abdelsalam Helal, Santosh Balakrishnan, Margaret Dunham, Ramez Elmasri

Department of Computer Science Technical Reports

No abstract provided.


On Neurobiological, Neuro-Fuzzy And Statistical Pattern Recognition Techniques, Anupam Joshi, Narendran Ramakrishnan, Elias N. Houstis, John R. Rice Jan 1996

On Neurobiological, Neuro-Fuzzy And Statistical Pattern Recognition Techniques, Anupam Joshi, Narendran Ramakrishnan, Elias N. Houstis, John R. Rice

Department of Computer Science Technical Reports

No abstract provided.


Average Profile Of Generalized Digital Search Trees And The Generalized Lempel-Ziv Algorithm, Guy Louchard, Wojciech Szpankowski, Jing Tang Jan 1996

Average Profile Of Generalized Digital Search Trees And The Generalized Lempel-Ziv Algorithm, Guy Louchard, Wojciech Szpankowski, Jing Tang

Department of Computer Science Technical Reports

No abstract provided.


Visualization Of Scalar Topology For Structural Enhancement, Chandrajit L. Bajaj, Daniel R. Schikore Jan 1996

Visualization Of Scalar Topology For Structural Enhancement, Chandrajit L. Bajaj, Daniel R. Schikore

Department of Computer Science Technical Reports

No abstract provided.


A Graph-Constructive Approach To Solving Systems Of Geomeric Constraints, Ioannis Fudos, Christoph M. Hoffmann Jan 1996

A Graph-Constructive Approach To Solving Systems Of Geomeric Constraints, Ioannis Fudos, Christoph M. Hoffmann

Department of Computer Science Technical Reports

No abstract provided.


Analysis Of A Splitting Process Arising In Probabilistic Counting And Other Related Algorithms, Peter Kirschenofer, Helmut Prodinger, Wojciech Szpankowski Jan 1996

Analysis Of A Splitting Process Arising In Probabilistic Counting And Other Related Algorithms, Peter Kirschenofer, Helmut Prodinger, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.


The Apic Approach To High Performance Network Interface Design: Protected Dma And Other Techniques, Zubin D. Dittia, Guru M. Parulkar, Jerome R. Cox Jr. Jan 1996

The Apic Approach To High Performance Network Interface Design: Protected Dma And Other Techniques, Zubin D. Dittia, Guru M. Parulkar, Jerome R. Cox Jr.

All Computer Science and Engineering Research

We are building a very high performance 1.2 Gb/s ATM network interface chip called the APIC (ATM Port Interconnect Controller). In addition to borrowing userful ideas from a number of research and commercial prototypes, the APIC design embraces several innovative features, and integrates all of these pieces into a coherent whole. This paper describes some of the novel ideas that have been incorporated in the APIC design with a view to improving the bandwidth and latency seen by end-applications. Among the techniques described, Protected DMA and Protected I/O were designed to allow applications to queue data for transmission or reception …


Efficient User Space Protocol Implementations With Qos Guarantees Using Real-Time Upcalls, R. Gopalakrishnan, Guru M. Parulkar Jan 1996

Efficient User Space Protocol Implementations With Qos Guarantees Using Real-Time Upcalls, R. Gopalakrishnan, Guru M. Parulkar

All Computer Science and Engineering Research

Real-time upcalls (RTUs) are an operating systems mechanism to provide quality-of-service (QoS) guarantees to network applications, and to efficiently implement protocols in user space with (QoS) guarantees. Traditionally, threads (and real-time extensions to threads) have been used to structure concurrent activities in user space protocol implementations. However, preemptive scheduling required for real-time threads leads to excessive context switching, and introduces the need for expensive concurrency control mechanisms such as locking. The RTU mechanism exploits the iterative nature of protocol processing to eliminate the need for locking, and reduce asynchronous preemption, while ensuring real-time operation. In addition to efficiency, eliminating the …