Physical Sciences and Mathematics Commons^™

Solving The Region Growing Problem On The Connection Machine, Nawal Copty, Sanjay Ranka, Geoffrey C. Fox, Ravi Shankar

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

This paper presents a parallel algorithm for solving the region growing problem based on the split and merge approach. The algorithm was implemented on the CM-2 and the CM-5 in the data parallel and message passing models. The performance of these implementations is examined and compared.

Genetic Algorithms For Stochastic Flow Shop No Wait Scheduling, Harpal Maini, Ubirajara R. Ferreira

Electrical Engineering and Computer Science - Technical Reports

ln this paper we present Genetic Algorithms - evolutionary algorithms based on an analogy with natural selection and survival of the fittest - applied to an NP Complete combinatorial optimization problem: minimizing the makespan of a Stochastic Flow Shop No Wait (FSNW) schedule. This is an important optimization criteria in real-world situations and the problem itself is of practical significance. We restrict our applications to the three machine flow shop no wait problem which is known to be NP complete. The stochastic hypothesis is that the processing times of jobs are described by normally distributed random variables. We discuss how …

Binary Resolution In Surface Reasoning, William C. Purdy

Electrical Engineering and Computer Science - Technical Reports

Intuition suggests the hypothesis that everyday human reasoning is conducted in the written or spoken natural language, rather than in some disparate representation into which the surface language is translated. An examination of human reasoning reveals patterns of inference that parallel binary resolution. But any standard implementation of resolution requires Skolemization. Skolemization would seem an unlikely component of human reasoning. This appears to contradict the hypothesis that human reasoning takes place at the surface. To reconcile these observations, this paper develops a new rule of inference, which operates on surface expressions directly. This rule is shown to produce results which …

Multimedia Object Modelling And Storage Allocation Strategies For Heterogeneous Parallel Access Storage Devices In Real Time Multimedia Computing Systems, C.Y. Roger Chen, Kingsley C. Nwosu, P. B. Berra

Electrical Engineering and Computer Science - All Scholarship

The improvements in disk speeds have not kept up with improvements in processor and memory speeds. Conventional storage techniques, in the face of multimedia data, are inefficient and/or inadequate. Here, an efficient multimedia object allocation strategy is presented. We describe a multimedia object model, the object and storage device characteristics, and the fragmentation strategy. A bipartite graph approach is used for mapping fragments to storage devices and a cost function is used to determine an efficient allocation of an object and to balance the loads on the devices.

Architectural Support For High-Performance Distributed Computing, Jongbaek Park, Salim Hariri

Electrical Engineering and Computer Science - All Scholarship

The emergence of high speed networks and the proliferation of high performance workstations have attracted a lot of interest in workstation-based distributed computing. Current trend in local area networks is toward higher communication bandwidth as we progress from Ethernet networks that operate at 10 Mbit/sec to higher speed networks that can operate in Gbit/sec range. Also, current workstations are capable of delivering tens and hundreds of Megaflops of computing power. By using a cluster of such high-performance workstations and the high-speed networks, a high-performance distributed computing environment could be built in cost-effective manner as an alternative of supercomputing platform. However, …

Software And Hardware Support For Workstation-Based, Salim Hariri, Manish Parashar, Jongbaek Park

Electrical Engineering and Computer Science - All Scholarship

The proliferation of high performance workstations and the emergence of high speed networks have attracted a lot of interest in workstation-based supercomputing. We project that workstation-based environments with supercomputing capabilities will be available in the not-so-distant future. However a number of hardware and software issues have to be resolved before the full potential of these workstation-based supercomputing environments can be exploited. The presented research has two main objectives: (1) to investigate the limitations of communications techniques used in current workstation-based systems and to identify a set of requirements that must be satisfied to achieve workstation-based supercomputing; (2) to use these …

Asymptotically Tight Bounds For Performing Bmmc Permutations On Parallel Disk Systems, Thomas H. Cormen, Leonard F. Wisniewski

Computer Science Technical Reports

No abstract provided.

Approximation Algorithms For Configuring Hierarchical Nonblocking Communication Networks, J. Andrew Fingerhut

All Computer Science and Engineering Research

A framework is given for specifying nonblocking traffic limits in a connection-oriented communications network. In this framework, connections may be point-to-point or mutlipoint, and the data rates may vary from one connection to another. The traffic limits may be "flat", or they may also be hierarchical, representing communities of interest within the network that have higher traffic among themselves than with the rest of the network. The communication networks are constructed from switches (or nodes) and trunks, which connect pairs of switches. This framework is intended to model Asynchronous Transfer Mode (ATM) networks and traffic. We present a way of …

Segmentation/Recognition Of Hand-Written Numeral Characters, Khalid Sherdil

All Computer Science and Engineering Research

This thesis describes a number of techniques for segmenting non-cursive handwritten digits into individual characters. It strongly emphasizes on a recognition-segmentation algorithm, which uses the linear regression method to recognize those strokes which consist of one or more straight-lined parts. A new method of sampling the pen data according to the pen speed, hence giving a more uniform points concentratino distribution, is also introduced. It is shown how several of our segmenting techniques, such as relative stroke lengths, relative stroke positions, order of stroke entry, stroke direction, stroke intersection, etc. can be combined to yield success results of about 95%.

Symphony: A Hardware, Operating System, And Protocol Processing Architecture For Distributed Multimedia Applications, Andreas D. Bovopoulos, R. Gopalakrishnan, Saied Hosseini

All Computer Science and Engineering Research

This paper explores the architectural requirements for computers to be able to process multimedia data streams such as video and audio. The I/O subsystem is shown to be a bottleneck, and a network backplane approach is suggested to alleviate this. The need to provide end-to-end performance guarantees requires predictable performance of intra-machine communication, and a schedulable bus with reservation is proposed to achieve this. In addition this requires operating system (OS) mechanisms to negotiate and enforce QoS requirements of applications. A real-time microkernel executive is proposed for each autonomous unit. Requirements for real-time microkernel exeutive is proposed for each autonomous …

Clothespins On Timelines: Utilities And The Interval Representation Of Time, R. P. Loui, Jersey Chen

All Computer Science and Engineering Research

We discuss the problem of representing utility in planning systems that are based on Allen's [83] popular ontology for planning, which represents actions and events as time intervals. We identify a small number of primitive functions on time intervals which may be helpful in representing preference and also in eliminating dominated actions. Assuming that utility can be decomposed to take advantage of these primitives, these functions provide one solution to the problem of specifying utility in such expressive planning languages. We identify a restricted class of utility expressions that generate linear programming problems. The contribution is not deep, but is …

An Optimal Algorithm For Shortest Paths On Weighted Interval And Circular-Arc Graphs With Applications, Mikhail J. Atallah, Danny Z. Chen, D. T. Lee

Department of Computer Science Technical Reports

No abstract provided.

Distributed Modeling And Rendering Of Splines Using Ganith And Splinex, Chandrajit L. Bajaj, Jindon Chen, Susan B. Evans

Department of Computer Science Technical Reports

No abstract provided.

Modeling With A-Patches, Chandrajit L. Bajaj, Jindon Chen, Guoliang Xu

Department of Computer Science Technical Reports

No abstract provided.

Preconditioner Construction With Rational Approximation, Mo Mu, John R. Rice

Department of Computer Science Technical Reports

No abstract provided.

Topologically Correct Approximations Of Arbitrary Rational Parametric, Chandrajit L. Bajaj, Andrew V. Royappa

Department of Computer Science Technical Reports

No abstract provided.

On The Semantics Of Generative Geometry Representations, Christoph M. Hoffmann

Department of Computer Science Technical Reports

No abstract provided.

Collaborative Multimedia Scientific Design In Shastra, Vinod Anupam, Chandrajit L. Bajaj

Department of Computer Science Technical Reports

No abstract provided.

A Coarse-Grained, Architecture-Independent Approach For Connected Component Labeling, Mikhail J. Atallah, Frank Dehne, Susanne E. Hambrusch

Department of Computer Science Technical Reports

No abstract provided.

A Unifying Approach To Hierarchical Transaction Management In Multidatabase Systems, Ahmed K. Almagarmid, Aidong Zhang

Department of Computer Science Technical Reports

No abstract provided.

Videoscheme: A Programmable Video Editing System For Automation And Media Recognition, James Matthews, Peter Gloor, Fillia Makedon

Computer Science Technical Reports

The recent development of powerful, inexpensive hardware and software support had made digital video editing possible on personal computers and workstations. To date the video editing application category has been dominated by visual, easy-to-use, direct manipulation interfaces. These systems bring high-bandwidth human-computer interaction to a task formerly characterized by slow, inflexible, indirectly-operated machines. However, the direct manipulation computer interfaces are limited by their manual nature, and can not easily accommodate algorithmically- defined operations. This paper proposes a melding of the common direct manipulation interfaces with a programming language which we have enhanced to manipulate digital audio and video. The result …

Reasoning About Synchrony Illustrated On Three Models Of Concurrency, Gruia-Catalin Roman, Jerome Plun

All Computer Science and Engineering Research

This paper presents a model of concurrency (Dynamic Synchrony) whose distinctive feature is a novel formal treatment of synchronization. Synchrony is defined as the coordinated execution of two or more actions. The dynamic aspect comes from the fact that the definition of which actions must be executed synchronously can change freely during the execution of the program. This unique modeling capability comes with a UNITY-stype assertional logic that can be applied to program verification and derivation. This paper shows that the proposed proof logic can be used to verify programs expressed using other models of foncurrency without having to translate …

The Programmers' Playground: I/O Abstraction For Heterogeneous Distributed Systems, Kenneth J. Goldman, Michael D. Anderson, Bala Swaminathan

All Computer Science and Engineering Research

I/O abstraction is offered as a new high-level approach to interprocess communication. Functional components of a concurrent system are written as encapsulated modules that act upon local data structures, some of which may be published for external use. Relationships among modules are specified by logical connections among their published data structures. Whenever a module updates published data, I/O takes place implicitly according to the configuration of logical connections. The Programmer's Playground, a software library and run-time system supporting I/O abstraction, is described. Design goals include high-level communication among programs written in multiple programming languages and the uniform treatment of discrete …

Trimming And Closure Of Constrained Surfaces, Xiangping Chen, Christoph M. Hoffmann

Department of Computer Science Technical Reports

No abstract provided.

New Software Composition Tools, Bruno Degazio

Publications and Scholarship

This paper briefly discusses a number of software tools developed at the author's studio through the course of research work into algorithmic composition. Most of the tools developed are directly related to recursive techniques; some, however, arise from more general techniques of algorithmic composition first described by Joseph Schillinger.

Examples of recursive techniques include:
• META-FRACTALS - separating musical content from recursive structure
• the Lorenz attractor and Koch snowflake as musical generators
• Iterated Function Systems as musical generator
• dynamic values in the logistic equation and the Mandelbrot set.

Non-recursive tools include:
• the Intelligent Interval Tool - …

Learning Unions Of Boxes With Membership And Equivalence Queries, Paul W. Goldberg, Sally A. Goldman, H. David Matthias

All Computer Science and Engineering Research

We present two algorithms that use membership and equivalence queries to exactly identify the concepts given by the union of s discretized axis-parallel boxes in d-dimensional discretized Euclidean space where each coordinate can have n discrete values. The first algorithm receives at most s*d counterexamples and uses time and membership queries polynomial in s and logn for d any constant. Further, all equivalence queries made can be formulated as the union of O(s*d*log(s)) axis-parallel boxes. Next, we introduce a new complexity measure that better captures the complexity of a union of boxes than simply the number of boxes and dimensions. …

The Dim System: Turn-Taking In Dyadic Telephone Dialogues, Umesh Berry, Anne Johnstone

All Computer Science and Engineering Research

The analysis of human conversations has revealed that the design of interfaces using spoken dialogue must differ radically from those using written communication. Such characteristics as prosody, confirmations, echoes, and other speech phenomena must be considered. This work is a step in that direction. Prosodic, syntactic and semantic information from actual human dialogues has been used to build a turn-taking model empirically for dydadic telephone dialogues. The ability to predict completion of turns has been the biggest motivating factor in the development of this model. The design and evaluation of the model are presented in this report.

Distributed Computing Systems And Checkpointing, Ken Wong, Mark Franklin

All Computer Science and Engineering Research

This paper examines the performance of synchronous checkpointing in a distributed computing environment with and without load redistribution. Performance models are developed, and optimum checkpoint intervals are determined. The analysis extends earlier work by allowing for multiple nodes, state dependent checkpoint intervals, and a performance metric which is coupled with failure-free performance and the speedup functions associated with implementation of parallel algorithms. Expressions for the optimum checkpoint intervals for synchronous checkpointing with and without load redistribution are derived and the results are then used to determine when load redistribution is advantageous.

Effective Loss Of Multiplexed Atm Cell Streams, Seyyed M-R Mahdavian, Andreas D. Bovopoulos

All Computer Science and Engineering Research

Cell loss is an inherent problem of ATM networks. The magnitude of the service degeneration caused by cell loss depends on the application and loss distribution. This paper introduces a new performance criterion, called effective loss, which can quantitatively measure this degradation. Effective loss is particularly suitable for block-oriented transmissions, such as file transfer applications, but can also be applied to a broad range of other applications. In this paper the effective loss measure is applied to the study of the effectiveness of bandwidth reservation mechanisms in an ATM multiplexer. Numerical results demonstrate circumstances under which bandwidth reservation improves performance …

Representing And Learning Propositional Logic In Symmetric Connectionist Networks, Gadi Pinkas

All Computer Science and Engineering Research

The chapter presents methods for efficiently representing logic formulas in connectionist networks that perform energy minimization. Algorithms are given for transforming any formula into a network in linear time and space and for learning representations of unknown formulas by observing examples of satisfying truth assignments. The relaxation process that underlies networks of energy minimization reveals an efficient hill climbing algorithm for satisfiability problems. Experimental results indicate that the parallel implementation of the algorithm with give extremely good average-case performance, even for large-scale, hard satisfiability problems (randomly generated).