Digital Commons Network^™

A Fast O(K) Multicast Message Routing Algorithm, Thomas J. Sager, Bruce M. Mcmillin

Computer Science Technical Reports

In many multicomputer applications is it necessary for one node to send an identical message to many nodes. One to many communications are called multicasts. Although broadcasts (one to all) and unicasts (one to one) have been widely implemented, multicasts, in spite of their importance to efficient use of multicomputer systems, have not received much attention.

Minimal traffic multicasting is equivalent to the minimal Steiner tree problem and is known to be NP-complete. Therefore, a heuristic polynomial time approximation must be used; but, to take advantage of advances in second generation multicomputer hardware such as wormhole routing, a distributed multicast …

Visualization Of Surfaces In Four-Dimensional Space, Christoph M. Hoffmann, Jianhua Zhou

Department of Computer Science Technical Reports

No abstract provided.

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, March 1990, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A sixteen page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

Computational Complexity Of Geometric Symmetry Detection In Graphs, Joseph Manning

Computer Science Technical Reports

Constructing a visually informative drawing of an abstract graph is a problem of considerable practical importance, and has recently been the focus of much investigation. Displaying symmetry has emerged as one of the foremost criteria for achieving good drawings. Linear-time algorithms are already known for the detection and display of symmetry in trees, outerplanar graphs, and embedded planar graphs. The central results of this paper show that for general graphs, however, detecting the presence of even a single axial or rotational symmetry is NP-complete. A number of related results are also established, including the #P-completeness of counting the axial or …

Mapping Finite Element Graphs On Hypercubes, Yeh-Ching Chung, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

In parallel computing, it is important to map a parallel program onto a parallel computer such that the total execution time of a parallel program is minimized. In general, a parallel program and a parallel computer can be represented by a task graph (TG) and a processor graph (PG), respectively. For a TG, nodes represent tasks of a parallel program and edges denote the data communication needed between tasks. The weights associated with nodes and edges represent the computational load and communication cost, respectively. For a PG, nodes and edges denote processors and communication channels, respectively. By using the graph …

An Architecture For Distributed Multimedia Database Systems, P. B. Berra, C.Y.R. Chen, A. Ghafoor, C. C. Lin

Electrical Engineering and Computer Science - All Scholarship

In the past few years considerable demand for user oriented multimedia information systems has developed. These systems must provide a rich set of functionality so that new, complex, and interesting applications can be addressed. This places considerable importance on the management of diverse data types including text, images, audio and video. These requirements generate the need for a new generation of distributed heterogeneous multimedia database systems. In this paper we identify a set of functional requirements for a multimedia server considering database management, object synchronization and integration, and multimedia query processing. A generalization of the requirements to a distributed system …

Using Annotated C++, Marshall P. Cline, Doug Lea

Electrical Engineering and Computer Science - All Scholarship

A++ (‘‘Annotated C++’’) is both a formalism and a proposed CASE tool for annotating C++ code with object-oriented specifications, assertions, and related semantic information. Annotations provide programmers with a useful means for approaching class design, exceptions, correctness, standardization, software reusability and related issues in software engineering with C++. This paper shows how A++ provides arbitrarily fine granularity to the C++ type system, how it automates and streamlines exception testing, how it can aid in standardization of software components, and how it can safely remove redundant exception tests.

Arithmetic Classification Of Perfect Models Of Stratified Programs (Addendum), Krzysztof R. Apt, Howard A. Blair

Electrical Engineering and Computer Science - Technical Reports

RECURSION-FREE PROGRAMS The following section completes the analysis of arithmetic complexity of perfect models and has been inadvertently omitted in the previous version of the paper. We say that a general program P is recursion-free if in its dependency graph Dp there is no cycle. Clearly recursion-free programs form a subclass of stratified programs. Recursion-free programs form a very simple generalization of the class of hierarchical programs introduced in [C78]. Hierarchical programs satisfy an additional condition on variable occurrences in clauses that prevents floundering, i.e. a forced selection of a non-ground negative literal in an SLDNF- derivation. In this section …

Faster Circuits And Shorter Formulas For Multiple Addition, Multiplication And Symmetric Boolean Functions, Michael Paterson, Uri Zwick, Nicholas Pippenger

All HMC Faculty Publications and Research

A general theory is developed for constructing the shallowest possible circuits and the shortest possible formulas for the carry-save addition of n numbers using any given basic addition unit. More precisely, it is shown that if BA is a basic addition unit with occurrence matrix N, then the shortest multiple carry-save addition formulas that could be obtained by composing BA units are of size n1p+o(1)/, where p is the unique real number for which the Lp norm of the matrix N equals 1. An analogous result connects the delay matrix M of the basic addition unit BA and the minimal …

Dawgs - A Distributed Compute Server Utilizing Idle Workstations, Henry Clark, Bruce M. Mcmillin

Computer Science Faculty Research & Creative Works

A collection of powerful workstations interconnected by a local area network can be utilized as compute servers when left idle by their owners. DAWGS allows users to submit jobs for execution on an idle workstation somewhere on a local area network. DAWGS uses a distributed scheduler and a bidding scheme to determine on which machine to run a process. DAWGS can properly redirect all the I/O of a remotely executing process and can checkpoint and then subsequently restart the process, even if the restart is on a different machine than the checkpoint. Our method is different from other work in …

Performance Analysis Of A Distributed File System, Meenakshi Mukhopadhyay

Dissertations and Theses

An important design goal of a distributed file system, a component of many distributed systems, is to provide UNIX file access semantics, e.g., the result of any write system call is visible by all processes as soon as the call completes. In a distributed environment, these semantics are difficult to implement because processes on different machines do not share kernel cache and data structures. Strong data consistency guarantees may be provided only at the expense of performance.

This work investigates the time costs paid by AFS 3.0, which uses a callback mechanism to provide consistency guarantees, and those paid by …

Educational Software Development Using Hypertext And Expert System Software Concepts, Siripong Malasri, Roger R. Easson

Journal of the Arkansas Academy of Science

This paper presents two computer software concepts: hypertext and expert systems; which are useful for educational software development. Good educational software enhances the learning process and offers opportunities for faculty to provide additional materials for independent studies, which would otherwise be impossible, due to the limited time and incredible growing rate of technological progress. The hypertext concept offers the students a non-linear learning style, while the expert system concept provides explanation facilities for students to probe the logic of the systems. Both approaches are extremely useful for educational software. With the proper tools, the courseware can be implemented easily and …

Measurement Of The C+ Decay-Asymmetry Parameter, Avery, P.; Et Al., M. Thulasidas

Research Collection School Of Computing and Information Systems

We report a measurement of polarization in the two-body decay c+, in nonresonant e+e- interactions from data taken with the CLEO detector. Using these data we have determined the parity-violating asymmetry decay parameter c to be -1.0-0.0+0.4. We see no evidence for significant c+ polarization.

Observation Of B-Meson Semileptonic Decays To Noncharmed Final States, Fulton, R.; Et Al., M. Thulasidas

Research Collection School Of Computing and Information Systems

No abstract provided.

Observation Of Iv(4=S) Decays Into Non-=Bba Final States Containing I Mesons, Alexander, J.; Et Al., M. Thulasidas

Research Collection School Of Computing and Information Systems

We report on the observation of ; mesons from T(4S) decays which are too energetic to come from 8 mesons. These events provide evidence for non-88 decays of the T (4S). The measured rate is B(T(4S)+fX)=0.22•0.06•0.041 for ; momentum above 2 GeV/c.

Exclusive And Inclusive Decays Of B Mesons Into Ds Mesons, D. Bortoletto, Manoj Thulasidas

Research Collection School Of Computing and Information Systems

We have studied the production of Ds mesons in the decays of B mesons at the Υ(4S) resonance. We report on the first observation of exclusive B-meson decays B->Ds−D*+, B→Ds−D+, and B→Ds−D0. We also present a new measurement of the branching ratio and the momentum spectrum for the inclusive decay B→DsX.

An Expert System To Convert Knowledge-Based Geological Engineering Systems Into Fortran, Ralph W. Wilkerson, Jill J. Cress

Computer Science Faculty Research & Creative Works

A knowledge-based geographic information system (KBGIS) for geological engineering map (GEM) production was developed in GoldWorks, an expert system development shell. Using this shell, the geological engineer is able to develop a rule base for a particular application that results in a valid GEM. However, this implementation failed as a practical production system due to the excessive execution time required to produce a GEM. To solve this problem, a conversion expert system was developed which accepted, as input, a KBGIS and produced, as output, the equivalent Fortran code. Two major objectives are accomplished as a result of this system: GEN …

Experimentation With Large-Grained Parallelism Using Local Area Networks, Ralph W. Wilkerson, Douglas E. Meyer

Computer Science Faculty Research & Creative Works

HIGHLAND, a distributed-memory parallel processing environment for heterogeneous local area networks, has been developed. Designed as both a teaching and a research tool, its purpose is to provide an effective mechanism by which a number of networked UNIX workstations, dissimilar in both vendor and performance, can be directly manipulated as a single, unified, multiprocessing system. Utilizing the MIT X-windows environment, HIGHLAND supports a highly interactive graphical interface through which a programmer can create, modify, and control complex systems of communicating processes

Highland: A Graph-Based Parallel Processing Environment For Heterogeneous Local Area Networks, Ralph W. Wilkerson, Douglas E. Meyer

Computer Science Faculty Research & Creative Works

No abstract provided.

Role Of Term Symmetry In E-Completion Procedures, Ralph W. Wilkerson, Blayne E. Mayfield

Computer Science Faculty Research & Creative Works

No abstract provided.

Experimental Comparison Of Bidding And Drafting Load Sharing Protocols, Andrew Ross, Bruce M. Mcmillin

Computer Science Faculty Research & Creative Works

In recent years, a dramatic rise in the number of personal workstations interconnected via local area networks has occurred in the workplace. These can be organized as distributed computing systems. The combined computing power of these systems are often greater than mainframes of a decade ago, and usually less expensive. There is a growing interest in harnessing this often-underutilized power. Researchers are focusing their attention on remote execution of processes as one solution. An additional topic of research is to balance a workload among a series of computers. Remote execution is made possible because the distributed operating system provides migration …

Computational Intelligence In Cad/Cam Applications, Chaman Sabharwal, Thomas G. Melson, Martin D. Fraser

Computer Science Faculty Research & Creative Works

This paper presents a fundamental, direct, and powerful approach to the surface/surface intersection problem in CAD/CAM applications. The algorithm is designed and implemented in three steps: a) Preprocessing- locate the potentially intersecting sections of the surfaces and decompose the surfaces into surface elements within specified flatness tolerance; b) Intersection- decompose the possibly intersecting pairs of surface elements into continuous surface triangulations to find the approximate intersections between the pairs of surface elements; c) Postprocessing-assemble the intersection primitives into curves of intersection, refine the accuracy of computed intersection points, and compact the intersection curves. This surface/surface intersection algorithm is applicable to …

Trellis-Coded Multidimensional Phase Modulation, S. S. Pietrobon, Robert H. Deng

Research Collection School Of Computing and Information Systems

A 2L-dimensional multiple phase-shift keyed (L×MPSK) signal set is obtained by forming the Cartesian product of L two-dimensional MPSK signal sets. A systematic approach to partitioning L×MPSK signal sets that is based on block coding is used. An encoder system approach is developed. It incorporates the design of a differential precoder, a systematic convolutional encoder, and a signal set mapper. Trellis-coded L×4PSK, L×8PSK, and L×16PSK modulation schemes are found for 1⩽L⩽4 and a variety of code rates and decoder complexities, many of which are fully transparent to discrete phase rotations of the signal set. The new codes achieve asymptotic coding …

Distributed Evaluation Of An Iterative Function For All Object Pairs On A Simd Hypercube, Fikret Erçal

Computer Science Faculty Research & Creative Works

An efficient distributed algorithm for evaluating an iterative function on all pairwise combinations of C objects on an SIMD hypercube is presented. The algorithm achieves uniform load distribution and minimal, completely local interprocessor communication.

The Development Of An Expert System For The Diagnosis Of Diseases In Fibre And Dairy Goats, Tim S. Roberts

Theses: Doctorates and Masters

This thesis details the development of an expert system for the diagnosis of diseases in fibre and dairy goats. Divided into five sections, five appendices, and a bibliography, this thesis centres on the methods used to build the expert system: the decisions taken at the outset of, and during the course of, development; some of the problems encountered, and the solutions to those problems. A detailed appraisal is made of the development process and suggestions are made for future developments over similar domains (for example, the diagnosis of diseases in animals other than goats). Much emphasis is placed on three …

Digital Image Processing Using Mathematical Morphology, Andrew Mehnert

Theses : Honours

This dissertation is a natural extension of my undergraduate research project entitled, "Digital Image Processing”. Whilst my undergraduate project dealt with a number of classical digital image filtering techniques such as spatial convolution and frequency domain filtering via the Fourier transform, this dissertation focuses on an alternative approach employing Mathematical Morphology. In contrast to classical filtering techniques, which often geometrically distort the original image, morphological operations, used sensibly, essentially preserve shape and geometry. Mathematical morphology therefore lends itself to image processing applications requiring the identification of objects and object features within an image. Herein basic morphological operations are developed, firstly …

Development Of An Expert System To Convert Knowledge-Based Geological Engineering Systems Into Fortran, Jill J. Cress, Ralph W. Wilkerson

Computer Science Technical Reports

A knowledge-based geographic information system (KBGIS) for geological engineering map (GEM) production was developed in GoldWorks, an expert system development shell. GoldWorks allows the geological engineer to develop a rule base for a GEM application. Implementation of the resultant rule base produced a valid GEM, but took too much time. This proved that knowledge-based GEM production was possible but in GoldWorks implementation failed as a practical production system. To solve this problem, a Conversion Expert System was developed which accepted, as input, a KBGIS and produced, as output, the equivalent Fortran code. This allowed the engineer to utilize GoldWorks for …

The Directed Steiner Problem On Graphs: A Simulated Annealing Approach, Lawrence Joseph Osborne, Billy E. Gillett

Computer Science Technical Reports

The well-known Steiner Problem on Graphs is an NP-complete problem for which there are many heuristic and exact algorithms that are deterministic. In this dissertation a new approach to the directed version of this problem is made by applying the ideas of statistical mechanics through the use of the method of simulated annealing. A version of annealing is developed for the Directed Steiner Problem and compared with one of the best general annealing schemes. Then a comparison is made between simulated annealing and the traditional branch and bound technique. The dual ascent algorithm of Richard T. Wong is used to …

Ua66/3/2 Computer Science Alumni Newsletter, Vol. 5, Wku Computer Science

WKU Administration Documents

Newsletter created by WKU Computer Science for the alumni of the program.

On The Height Of Digital Trees And Related Problems, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.