Digital Commons Network^™

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 Efficient Runge-Kutta (4,5) Pair, P. Bogacki, L. F. Shampine

Mathematics & Statistics Faculty Publications

A pair of explicit Runge-Kutta formulas of orders 4 and 5 is derived. It is significantly more efficient than the Fehlberg and Dormand-Prince pairs, and by standard measures it is of at least as high quality. There are two independent estimates of the local error. The local error of the interpolant is, to leading order, a problem-independent function of the local error at the end of the step.

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 …

Designing Minimum Cost Nonblocking Communication Networks, J. Andrew Fingerhut, Subhash Suri, Jonathan S. Turner

All Computer Science and Engineering Research

This paper addresses the problem of topological design of ATM (and similar) communication networks. We formulate the problem from a worst-case point of view, seeking network desings that, subject to specified traffic constraints, are nonblocking for point-to-point and multicast virtual circuits. Within this model we give various conditions under which star networks are optimal or near-optimal. These conditions are approximately satisfied in many common situations making the results of practical significance. An important consequence of these results is that, where they apply, there is no added cost for nonblocking multicast communication, relative to networks that are nonblocking for point-to-point traffic …

An Algorithm For Message Delivery To Mobile Units, Amy L. Murphy, Gruia-Catalin Roman, George Varghese

All Computer Science and Engineering Research

With recent advances in wireless communication and the ubiquity of laptops, mobile computing has become an important research area. An essential problem in mobile computing is the delivery of a message from a source to either a single mobile node, unicast, or to a group of mobile nodes, multicast. Standard solutions used in Mobile IP and cellular phones for the unicast problem rely on tracking the mobile unit. Tracking solutions scale badly when mobile nodes move frequently, and do not generalize well to multicast delivery. Our paper proposes a new message delivery algorithm for micromobility based on a modification of …

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 …

An Investigation Into An Effective Method Of Automatically Analysing Oracle Applications To Count Function Points, J. L. Wong

Theses : Honours

Function Point Analysis (FPA) is a synthetic software estimation metric used for computing the size and complexity of applications. It was first introduced by Allan. J. Albrecht during the mid-seventies, as a result of a lengthy research based on applications that were developed using COBOL and PL/1 programming languages. The purpose of this research· is to investigate the possibility, and the most effective method, of automatically performing a Function Point Analysis on Oracle applications that consist of Oracle Forms and Oracle Reports. The research revealed a seemingly lack of other researches on this topic. As FPA was invented a few …

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.

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

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

Department of Computer Science Technical Reports

No abstract provided.

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

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

Department of Computer Science Technical Reports

No abstract provided.

Customer Feedback Information System For Quality Improvement, Ke Wang

Masters Theses

This research addressed the basic needs for an effective customer feedback information system and the database technology to develop the system. It discussed the system concept and configuration of a typical customer feedback information system, database management technology, programming flow charts, program functions and capabilities. A proposed customer feedback information system consists of customer data inputs, database management system and outputs to various departments in an organization. With a user-friendly interface, database management system serves as an information management tool. It can process the feedback from customers and use the information in decision making. Thus, customer feedback can be promptly …

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 …

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.

A Family Of Parallel Runge-Kutta Pairs, P. Bogacki

Mathematics & Statistics Faculty Publications

Increasing availability of parallel computers has recently spurred a substantial amount of research concerned with designing explicit Runge-Kutta methods to be implemented on such computers. Here, we discuss a family of methods that require fewer processors than methods presently available do, still achieving a similar speed-up. In particular, (5,6) and (6,7) pairs are derived, that require a minimum number of function evaluations on two and three processors, respectively.

Simulator For The Performance Analysis Of Cpm Schemes In An Indoor Wireless Environment, Ronald Chua

Theses : Honours

A software simulator for characterising Continuous Phase Modulation (CPM) schemes in an indoor multipath environment has been developed using SIMULINK and MATLAB. The simulator is capable of simulating a wide range of CPM schemes to determine bandwidth efficiency and robustness to additive white Gaussian noise (AWGN) and Rician fading. Initial trials of the simulator indicate that the simulator is functioning correctly. Eventually, the simulator will be used to determine the most suitable modulation scheme for the development of an actual indoor wireless system.

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 …

Arbitrary Views Of High-Dimensional Space And Data, Andrew Ellerton

Theses : Honours

Computer generated images of three dimensional scenes objects are the result of parallel/perspective projections of the objects onto a two dimensional plane. The computational techniques may be extended to project n-dimensional hyperobjects onto (n-1) dimensions, for n > 3. Projection to one less dimension may be applied recursively for data of any high dimension until that data is two-dimensional, when it may be directed to a computer screen or to some other two-dimensional output device. Arbitrary specification of eye location, target location, field-of-view angles and other parameters provide flexibility, so that data may be viewed-and hence perceived-in previously unavailable ways. However, …

The Design And Implementation Of A Toolkit For The Creation Of Virtual Environments, Jesse Kinross-Smith

Theses : Honours

Virtual Reality is a field that is steadily increasing in popularity and interest. New developments in both hardware and software have empowered developers with new devices allowing faster and better quality interaction with virtual environments. However, the emphasis of research in virtual environments has been more concerned with development of new display and input devices, as opposed to the investigation of different methods of interaction that a three-dimensional environment offers. This project designs and implements a three-dimensional, interactive, virtual environment development system upon an existing three-dimensional rendering engine. The aim of the project is to allow users to generate virtual …

A Policy-Independent Secure X Server, Kirk Joseph Bittler

Dissertations and Theses

This thesis demonstrates that a secure X system can be designed and implemented to be independent of a particular security policy. The advantages and costs of a separation of security policy and enforcement are examined by developing a large scale application, the DX windowing system, on a DTOS platform. DTOS is a high assurance operating system that isolates policy decisions in a Security Server. A security conscious process, such as DX, eliminates policy considerations from the code. The process instead consults the Security Server and enforces the decisions that server derives from the policy. The DX architecture is described and …

Embedded Particle Computation In Evolved Cellular Automata, Wim Hordijk, James P. Crutchfield, Melanie Mitchell

Computer Science Faculty Publications and Presentations

In our work we are studying how genetic algorithms (GAs) can evolve cellular automata (CAs) to perform computations that require global coordination. The evolving cellular automata" framework is an idealized means for studying how evolution (natural or computational) can create systems that perform emergent computation, in which the actions of simple components with local information and communication give rise to coordinated global information processing [3].

In previous work [4, 5], we analyzed the process by which a genetic algorithm designed CAs to perform particular tasks. In this paper we focus on how these CAs implement the emergent computational strategies for …

Parallel Newton-Krylov-Schwarz Solvers For The Full Potential Flow Equation, Jie Zhang

Computer Science Theses & Dissertations

Newton-Krylov-Schwarz methods are increasingly applied in Computational Fluid Dynamics (CFD). We develop a parallel analysis code based on this method for the full potential flow model. The full potential model consists of a single nonlinear second-order partial differential equation of mixed type (elliptic/hyperbolic), which we solve as a steady boundary-value problem.

We use a nine-point finite-difference stencil to discretize the equation. A Newtonlike linearization and correction method is used to solve the resulting set of nonlinear algebraic equations. To solve the inner linear equations, we employ a Krylov space method. Preconditioners are used to improve the convergence rate. In order …

An Adaptive Fuzzy Logic Controller For Intelligent Networking And Control, Irshad Nainar

Theses: Doctorates and Masters

In this thesis, we present a fuzzy logic control scheme to regulate the flow of traffic approaching a set of intersections. An adaptive Fuzzy Logic Traffic Controller (FLTC) is used to adjust the green phase split of the north-south and east-west approaches of a set of traffic signals based on the actual traffic approaching the intersection. Each intersection is coordinated with its neighbouring intersections by adjusting the offset of the local intersection. The offset is adjusted by a local fuzzy logic controller loacted at each intersection. A new fuzzy control scheme, using a supervisory Fuzzy Logic Controller, is also proposed …

A Search Tool To Enhance The Selection And Utilisation Of Reusable Software Modules Within The Object-Oriented Paradigm, Robert H. Cross

Theses: Doctorates and Masters

The affinity for reuse within the object-oriented paradigm may enable high levels of productivity; however, gains will become realisable only if a systems developer has access to tools which aid in the selection of classes. A method for object-oriented analysis and design is detailed and its process is assisted by an object-oriented search tool based on reference and corporate library technology. The search tool contributes to the determination of suitable existing inheritable classes and an explanation of its construction and use is included. A practical demonstration of the method, using the search tool, is elaborated. The thesis demonstrates that text …