Digital Commons Network^™

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 …

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.

Technical-Legal Aspects Of Software Patents, Kenneth Nolan Nichols

Theses Digitization Project

No abstract provided.

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 …

An Assessment Of Asynchronous Transfer Mode (Atm) Training For Educators, Dan A. Niswander

CCAC Theses and Dissertations

The purpose of this dissertation was to develop and evaluate a hypertext-based training tutorial/guide on asynchronous transfer mode (ATM) technology for use by school district educators and technology planners. A review of literature indicated training needs on new broadband technologies were not being adequately met from the point of view of an educational environment. An interactive hypertext solution was proposed, designed, and developed based on the needs of adult learners. An analysis of these needs indicated adults prefer flexibility in navigating between training topics as well as in the pace of material presentation, that is, whether to proceed at a …

Low Cost Video For Distance Education, Michael J. Simpson

CCAC Theses and Dissertations

A distance education system has been designed for Nova Southeastern University (NSU) . The design was based on emerging low cost video technology. The report presented the design and summarizes existing distance education efforts and technologies.

The design supported multimedia electronic classrooms, and enabled students to participate in multimedia classes using standard telephone networks. Results were presented in three areas: management, courseware, and, systems.

In the area of management, the report recommended that the University separately establish, fund, and staff the distance education project. Supporting rationale was included.

In the area of courseware, the importance of quality courseware was highlighted. …

A Review Of Commercial And Research Cluster Management Software, Mark Baker, Geoffrey C. Fox, Hon W. Yau

Northeast Parallel Architecture Center

In the past decade there has been a dramatic shift from mainframe or ‘host-centric’ computing to a distributed ‘client-server’ approach. In the next few years this trend is likely to continue with further shifts towards ‘network-centric’ computing becoming apparent. All these trends were set in motion by the invention of the mass-reproducible microprocessor by Ted Hoff of Intel some twenty-odd years ago. The present generation of RISC microprocessors are now more than a match for mainframes in terms of cost and performance. The long-foreseen day when collections of RISC microprocessors assembled together as a parallel computer could outperform the vector …

An Application Perspective On High-Performance Computing And Communications, Geoffrey C. Fox

Northeast Parallel Architecture Center

We review possible and probable industrial applications of HPCC focusing on the software and hardware issues. Thirty-three separate categories are illustrated by detailed descriptions of five areas -- computational chemistry; Monte Carlo methods from physics to economics; manufacturing; and computational fluid dynamics; command and control; or crisis management; and multimedia services to client computers and settop boxes. The hardware varies from tightly-coupled parallel supercomputers to heterogeneous distributed systems. The software models span HPF and data parallelism, to distributed information systems and object/data flow parallelism on the Web. We find that in each case, it is reasonably clear that "HPCC works …

The Distributed Array Descriptor For A Pcrc Hpf Compiler Version 2.0 Sccs-770d, Bryan Carpenter, James Cowie, Donald Leskiw, Xiaoming Li

Northeast Parallel Architecture Center

We describe a distributed array descriptor that can be used by a runtime supporting HPFlike compilers. This descriptor captures all five types of alignment and BLOCK and CYCLIC distribution as defined in HPF specification. In essence, this descriptor does not distinguish whole array and array sections. Prior to this version, we had versions 1.0, 1.1, and 1.2. This version is not only an update of previous versions, but more importantly it also directly reflects our current practice in an HPF compilation effort.

A Tale Of Two Applications On The Nii, Geoffrey C. Fox

Northeast Parallel Architecture Center

We describe the expected capability of the NII (as an evolution of the Internet) interns of five broad service areas---collaboration, multimedia information dissemination, commerce, metacomputing, and Webtop productivity. We illustrate the demands on these services and the technology implications by examination of two application areas---manufacture of complex systems, such as aircraft and crisis management, command and control.

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 …

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 …

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 …

Finding Paths In The Rotation Graph Of Binary Trees, Rodney O. Rogers

Retrospective Theses and Dissertations

A binary tree coding scheme is a bijection mapping a set of binary trees to a set of integer tuples called codewords. One problem considered in the literature is that of listing the codewords for n-node binary trees, such that successive codewords represent trees differing by a single rotation, a standard operation for rebalancing binary search trees. Then, the codeword sequence corresponds to an Hamiltonian path in the rotation graph R_n of binary trees, where each node is labelled with an n-node binary tree, and an edge connects two nodes when their trees differ by a …

Tau Leptonic Branching Ratios, D. Buskulic, M. Thulasidas

Research Collection School Of Computing and Information Systems

A sample of 62249 τ-pair events is selected from data taken with the ALEPH detector in 1991, 1992 and 1993. The measurement of the branching fractions for τ decays into electrons and muons is presented with emphasis on the study of systematic effects from selection, particle identification and decay classification. The results obtained are: B e = 17.79±0.12(stat)±0.06(syst)(%) and Bμ = 17.31±0.11(stat)±0.05(syst)(%). Combined with the most recent ALEPH determination of the τ lifetime, these results provide a relative measurement of the leptonic couplings in the weak charged current for transverse W bosons: ${cal G}_{ώ}/{cal G}_{e}=1.0002pm 0.0051$ and ${cal G}_{∢u}/{cal G}_{u}=0.9943pm …

Design Information Recovery From Legacy System Cobol Source Code: Research On A Reverse Engineering Methodology, Robert Lee Miller

CCAC Theses and Dissertations

Much of the software in the world today was developed from the mid-1960s to the mid- 1970s.This legacy software deteriorates as it is modified to satisfy new organizational requirements. Currently, legacy system maintenance requires more time than new system development. Eventually, legacy systems must be replaced. Identifying their functionality is a critical part of the replacement effort. Recovering functions from source code is difficult because the domain knowledge used to develop the system is not routinely retained. The source code is frequently the only reliable source of functional information.

This dissertation describes functional process information recovery from COBOL source code …

On The Complexity Of Manpower Shift Scheduling, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

We consider the shift assignment problem in manpower scheduling, and show that a restricted version of it is NP-hard by a reduction from 3SAT. We then present polynomial algorithms to solve special cases of the problem and show how they can be deployed to solve more complex versions of the shift assignment problem. Our work formally defines the computational intractibility of manpower shift scheduling and thus justifies existing works in developing manpower scheduling systems using combinatorial and heuristic techniques.

Improved Measurement Of The B0 And B+ Meson Lifetimes, D. Buskulic, M. Thulasidas

Research Collection School Of Computing and Information Systems

Updated measurements of the B0 and B+ meson lifetimes are presented. From a data sample of 1.72 million hadronic Z0 decays recorded during the period 1991 to 1993, a sample of approximately 1000 semileptonic B meson decays containing a D0, D+ or D*+ has been isolated. From the distribution of decay times in the different samples the lifetimes of the B0 and B+ mesons are determined to be 1.53±0.12±0.08 ps and 1.52±0.14±0.09 ps, respectively, where the first error is statistical and the second systematic. The ratio of the B+ to B0 lifetimes is measured to be 0.99±0.14+0.05−0.04, confirming expectations that …

Automatic Pcb Inspection Algorithms: A Survey, Madhav Moganti, Fikret Ercal, Cihan H. Dagli, Shou Tsunekawa

Computer Science Faculty Research & Creative Works

The importance of the inspection process has been magnified by the requirements of the modern manufacturing environment. In electronics mass-production manufacturing facilities, an attempt is often made to achieve 100% quality assurance of all parts, subassemblies, and finished goods. A variety of approaches for automated visual inspection of printed circuits have been reported over the past two decades. In this survey, algorithms and techniques for the automated inspection of printed circuit boards are examined. A classification tree for these algorithms is presented and the algorithms are grouped according to this classification. This survey concentrates mainly on image analysis and fault …

A User Interface For The Visualization And Manipulation Of Arrays, Jennifer Leopold, A. Ambler

Computer Science Faculty Research & Creative Works

The success of spreadsheets has shown that a visual representation of a 2D array greatly facilitates solving certain problems. However, spreadsheets are not general-purpose programming environments and are not suited to many problems that might naturally be solved using multi-dimensional arrays. Furthermore, spreadsheets employ a textual notation for cell references in formulas. This notation, which adds to the programmer''s burden by distinguishing between relative and absolute addressing, can be difficult to understand and is error-prone even for the most experienced users. In this paper, we present a user interface for multi-dimensional arrays within Formulate, a form-based visual programming language. This …

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 …

Randomized Approximation Of The Constraint Satisfaction Problem, Hoong Chuin Lau, Osamu Watanabe

Research Collection School Of Computing and Information Systems

We consider the Weighted Constraint Satisfaction Problem (W-CSP) which is a fundamental problem in Artificial Intelligence and a generalization of important combinatorial problems such as MAX CUT and MAX SAT. In this paper, we prove non-approximability properties of W-CSP and give improved approximations of W-CSP via randomized rounding of linear programming and semidefinite programming relaxations. Our algorithms are simple to implement and experiments show that they are run-time efficient.