leff@smu.UUCP (Laurence Leff) (12/14/89)
-----------------------------------------------------------------------------
88-CSE-1. ($1.50)
AN ON-LINE ARITHMETIC UNIT FOR BIT-PIPELINED RATIONAL ARITHMETIC*
Peter Kornerup David W. Matula**
Odense University Southern Methodist University
January 1988
We derive a binary version of an algorithm of Gosper to compute the sum,
difference, product, quotient and certain rational functions of two rational
operands applicable to integrated approximate and exact rational computation.
The arithmetic unit we propose is an eight register computation cell with
bit-serial input and output employing a binary continued fraction
representation of the rational operands. The operands and results are
processed in a most-significant-bit first on-line fashion with bit level
logic. Individual bits of the input/output in our binary continued fraction
representation are shown to correspond in a one-to-one manner with primitive
shift and shift-and-add/subtract operations on pairs of registers in the
computation cell. Extension to a redundant signed-bit format is shown
feasible towards the ultimate goal of achieving small on-line delay and near
uniform throughput in cascaded pipelined computation with these computation
cells.
~*A preliminary version of this paper was presented at the IEEE Eighth
~~Symposium on Computer Arithmetic, May 1987 (proceedings pp~204-211 and SMU
~~Tech Report 86-CSE-25). This paper is to appear in the special issue on
~~High-Speed Computer Arithmetic of The Journal of Parallel and Distributed
~~Computing in 1988.
**This research was partially supported by the National Science Foundation
~~under grant DCR-8315289.
-----------------------------------------------------------------------------
88-CSE-2. ($1.00)
DISTRIBUTED DESIGN THROUGH STEPWISE REFINEMENT -
AN IMPLEMENTATION REPORT
Branislav Meandzija, Somnath Banerjee William P.-C. Ho
Southern Methodist University USC/Los Angeles
January 1988
In previous work, we introduced a new formulation of open systems and an
attendant Artificial Intelligence method which is based on establishing
communications rules by defining the creation of communication rules. Our
approach minimizes assumptions about communications technologies, purposes,
and environments, thus providing a flexible communications standard. Instead
of being fixed and imposed, communication rules are custom designed for an
application through a dynamic distributed stepwise refinement process.
Systems exchange partially specified communication rules, and negotiate to
gradually define the communication rules of the final implementation. In
this paper, we report on the implementation of a prototype of this
distributed design process. Assuming that all partial specifications have
been propagated to a participating system, we show how this system derives
the final communications rules. We give as example the composition of three
partial specifications to a final complete specification.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
88-CSE-3. ($1.00)
Y.A.N.C. (Yet Another Network Compiler)
James Radigan Branislav Meandzija
Texas Instruments Southern Methodist University
January 1988
Archetype is a method for the automatic design, specification, and
implementation of protocol architectures. It is based on two specification
techniques. These are: (1) a descriptive, "natural language"-like abstract
specification technique and, (2) a data-driven, concurrency exploiting,
executable specification technique. Abstract specifications are
automatically transformed into executable specifications. In this article we
introduce YANC a network compiler that translates Archetype executable
specifications into C code. YANC has been developed along the lines of
traditional syntax directed translation. We give a conceptual description of
YANC and report on the usage of YANC and its ability to interface UNIX system
calls.
-----------------------------------------------------------------------------
88-CSE-4. ($1.25)
A PARALLEL ARCHITECTURE FOR SIGNAL PROCESSING AND
LINEAR OPTIMIZATION ALGORITHMS*
Behrooz Shirazi
January 1988
The purpose of this project is twofold. First, it addresses the design
issues, the execution model, and the performance evaluation of a proposed
dataflow machine for signal processing and optimization algorithms. Second,
it investigates the application of simplex optimization techniques to the
problem of static task allocation in the proposed environment.
* This research is supported in part by the DARPA under contract 5-25089-310.
------------------------------------------------------------------------------
88-CSE-5. ($1.75)
SIMULATION OF A MAIN MEMORY DATABASE BASED ON THE WISCONSIN BENCHMARKS*
Chin-Feng Fan, Wei-Li Sun, Margaret H. Eich, Murat M. Tanik
January 1988
Simulation of a main memory database system based on Wisconsin
Benchmarks is described. Approaches used in simulation of parallelism, query
processing and checkpointing as well as the implementation of two-phase
locking are presented. A query network has been set up as a simulation
environment for the Wisconsin Benchmarks which can be adopted by any database
simulation. SLAM II on the IBM 3081 computer is used as the simulation
environment.
*~Revised version appears in the Proceedings of the Nineteenth Annual
~~Modeling and Simulation Conference, May 5-6, 1988, Pittsburgh, PA.
------------------------------------------------------------------------------
-----------------------------------------------------------------------------
88-CSE-6. ($1.00)
NONVOLATILE MAIN MEMORY: AN OVERVIEW OF ALTERNATIVES*
Margaret H. Eich, Wei-Li Sun
January 1988
A brief comparison of nonvolatile memory alternatives indicates that a
BBRAM is the best choice for the nonvolatile memory unit in an MMDB.
* This work was partially supported by NSF Grant IRI-87l3654.
-----------------------------------------------------------------------------
88-CSE-7. ($1.00)
MARS SHADOW MEMORY: A GOOD IDEA*
Margaret H. Eich
January 1988
Perhaps the most unusual feature of the MARS main memory database design
is the use of a shadow memory located in a nonvolatile stable memory.
Updates are made to this shadow memory rather than the volatile main memory,
eliminating the need for BFIM values in the log as well as reducing the time
required for transaction undo in the event of transaction aborts. In this
paper we provide an analysis which justifies the use of the shadow concept
even if the access time associated with the stable memory is higher than that
of the main memory.
* This work was partially supported by NSF Grant IRI-8713654.
-----------------------------------------------------------------------------
88-CSE-8. ($1.25)
COMPUTER INTEGRATED MANUFACTURING - AN INTRODUCTION
Kevin Kirkendall, M. M. Tanik
February 1988
The success factors, costs, and benefits of implementing the eight key
elements of a Computer Integrated Manufacturing System are described. The
social and economic factors affecting the current manufacturing environment
are taken into consideration as well.
-----------------------------------------------------------------------------
88-CSE-9. ($1.00)
APPROACHING EXECUTABLE SPECIFICATIONS
Terry Welch M. M. Tanik
ISSI SMU
February 1988
This discussion examines the characteristics expected in executable
specifications, the usage to which they will be put, and then some desirable
features we feel will contribute to achieving a workable system.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
88-CSE-10. ($1.00)
DESCRIBING REAL TIME SYSTEMS USING PPA AND XYZ/E
Jianbai Wang, Murat M. Tanik
February 1988
PPA is a kind of data-flow diagram system enhanced with process port
concept. XYZ/E is a temporal logic based language system. In order to
investigate the capability of these two approaches in describing real time
systems, a cruise control system example is described using PPA and the
result is transformed to XYZ/E description.
-----------------------------------------------------------------------------
88-CSE-11. ($1.00)
THE DESIGN OF A MESSAGE SWITCHING SYSTEM:
SOFTWARE REUSABILITY APPLIED TO DISCRETE EVENT SIMULATION
W. P. Yin, M. M. Tanik
February 1988
This paper proposes a framework for software system design. The
framework is based on the decomposition and abstraction. The design
formalism will employ an Object Descriptive Attributed Notation (ODAN) for
software design representation which records three types of primary
information of software system detail design: the decomposition hierarchy (of
the system being designed), the taxonomic structure (recognizing the
construction and function similarities), and the coupling specification
(specifying the way of component integration). A message switching
simulation system will be taken as an example during the discussion. An Ada
program based on this design is also presented.
-----------------------------------------------------------------------------
88-CSE-12. ($1.00)
COMPUTER INTEGRATED MANUFACTURING: A SURVEY OF CONCEPTS
M. Todd Foltz, M. M. Tanik
February 1988
A brief introduction to Computer Integrated Manufacturing is given. The
different components of Computer Integrated Manufacturing, where they are
located, and the availability to the business are discussed. In addition, we
examine why companies do not automate and discuss the reasons why a company
should implement CIM. Several strategies businesses can take to integrate
computers into their company are also discussed. Finally, we examine several
actual cases of CIM implementation.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
88-CSE-13. ($1.00)
SOFTWARE DESIGN REPRESENTATION:
OBJECT DESCRIPTIVE ATTRIBUTED NOTATION (ODAN)
W. P. Yin, M. M. Tanik, D. Y. Y. Yun
February 1988
This paper introduces a conceptual framework for constructing
operational software system design. The work is based upon the frame-based
representation and object-oriented design methodology. This design is called
Object Descriptive Attributed Notation (ODAN) which records three types of
primary information of software detail design: the decomposition hierarchy
(of the system being designed), the taxonomic structure (recognizing the
construction and function similarities) and the coupling specification
(specifying the way of component integration). In this paper, we also
describe a particular environment of this design framework, ART (The
Automated Reasoning Tool)* on TI Explorer. In this environment, the design
representation can be saved, retrieved and reasoned as software design
knowledge.
* ART (The Automated Reasoning Tool) Reference Manual, Inference
Corporation, Los Angeles, CA, 1986.
-----------------------------------------------------------------------------
88-CSE-14. ($1.00)
SIMULATION OF A MESSAGE SWITCHING SYSTEM WITH ADA OBJECTS
W. P. Yin, M. M. Tanik
March 1988
Ada is a general-purpose programming language with considerable
expressive power. It is a language that embodies and enforces the modern
software engineering principles of abstraction, information hiding,
modularity, and locality. Following an object-oriented design technique,
this paper illustrates the use of Ada for the design and implementation of a
message switching simulation system. Message switching simulation poses a
number of interesting problems: a high degree of concurrent activity, a
variety of I/O devices to be controlled, and messages with multiple
destinations. In this paper, we will discuss how Ada is used in an
object-oriented fashion in solving these problems.
-----------------------------------------------------------------------------
88-CSE-15. ($1.25)
GRAPHICAL PROGRAMMING:
AN INTRODUCTION AND A GRAPHICAL PASCAL TEACHING TOOL
Nirav Patel, Murat M. Tanik
March 1988
This paper surveys a fairly new practice in Computer Science --
programming with the aid of graphics tools. Although various diagramming
tools have been used for a long time, the decrease in the cost of graphics
hardware and memory is allowing the diagramming to be performed on the
computer instead of on paper. This paper looks at some of the advantages of
programming with graphics over conventional textual programming. Also, a
simple classification scheme of the various tools which support graphics
programming is introduced. Next, four tools which exemplify some of the
aspects of graphics programming are surveyed. Details of their capabilities,
and differences from other tools are discussed. Also, some of their
shortcomings are discussed. As a detailed example of a graphical programming
tool, the implementation and design of Jigsaw Pascal, a Pascal teaching
system currently being developed by the author, is discussed.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
88-CSE-16. ($10.00)
AN ADA COURSEWARE
Murat M. Tanik Udo W. Pooch
Southern Methodist University Texas A&M University
March 1988
Early research on developing self-paced courses have identified features
such as:~1)~individually paced,~~2)~mastery-oriented,~~3)~use of study guides
for communication of information, and 4) lectures for the purpose of
stimulation and motivation. In developing this computer-aided Ada course we
included most of these features. In addition, we used ACM Curriculum
recommendations as a course development guideline.
-----------------------------------------------------------------------------
88-CSE-17. ($1.00)
OBJECT ORIENTED PROGRAMMING IN A SHARED MEMORY MULTIPROCESSING ENVIRONMENT*
M. G. Christiansen, M. M. Tanik, S. L. Stepoway
March 1988
A programming methodology for parallel applications is presented that
relies on object oriented programming techniques. This work differs in that
the object oriented techniques are applied to a shared memory multiprocessing
environment. These techniques are used to implement shared data structures
and processing agents. The use of a statically typed object language
provided excellent execution times and speedups for multiple processing
elements. A case study is presented in which the object oriented approach is
compared to Fortran producing better performance and more
easily understood source code.
*~This research was supported in part by the DARPA under contract
MDA903-86-C-0182.
-----------------------------------------------------------------------------
88-CSE-18. ($1.00)
DESIGN AND IMPLEMENTATION ISSUES FOR AN OBJECT-BASED
DISTRIBUTED SOFTWARE ENGINEERING SUPPORT SYSTEM
M. G. Christiansen and M. M. Tanik
March 1988
Current developments in VLSI technology have enabled the development of
low cost processors and memories. The availability of these components have
generated interest in distributed and parallel processing applications, and
has made available many new architectures. But little advancement has been
made in providing software engineering support for distributed applications.
The major objective of this work is the development of a software
engineering support system for distributed applications. The key feature of
this support is the use of object programming in the definition of
applications. The use of an object paradigm provides several advantages over
conventional approaches to program design. We shall see that this approach
is particularly well suited for the development of distributed applications.
Because distributed applications are in reality a set of cooperating
processors, another goal of this support system is the abstraction of
processes into objects that are managed by the software engineer. The system
supports partitioning the application into a hierarchy of software objects
called "Applications," "Abstract Processing Elements," and "Objects" are
distributed and executed in a network of processing elements.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
88-CSE-19. ($1.00)
OBJECT-ORIENTED FRACTAL MODELING ON A SHARED-MEMORY MIMD MACHINE*
Stephen L. Stepoway and Michael G. Christiansen
March 1988
Fractal surfaces are a useful model for terrain in computer graphics,
but are computationally expensive. The high degree of parallelism present
makes them natural for implementation on MIMD architectures. We present a
study of using an object-oriented approach to implement a parallel fractal
terrain generation system on a shared memory multiprocessor. Although not
often thought of in connection with a shared memory environment, we
demonstrate how the object paradigm (specifically C++) adapts well to this
kind of architecture. The resulting system achieves high absolute
performance and a near-linear speedup using a novel load-balancing technique.
* This research was supported in part by DARPA under contract
MDA903-86-C-0182.
-----------------------------------------------------------------------------
88-CSE-20. ($1.00)
LIMITED-OR (LOR) PARALLEL EXECUTION: AN EFFECTIVE SCHEME FOR
HARNESSING PARALLELISM IN LOGIC PROGRAMS*
Shyh-Chang Su and Prasenjit Biswas
March 1988
The excessive processing overhead of implementing a combination of
unlimited AND/OR parallelism has been observed by a number of researchers.
The major problems associated with the implementation of unrestricted
OR-parallelism are related to efficient management of multiple binding
environments and the exponential growth in number of processes. Several
abstract processing models have been proposed to deal with the first problem.
In this report we propose a demand driven OR parallel execution scheme --
Limited OR-parallelism. The scheme does not suffer from the processing
overhead related to both the problems mentioned above and has been found to
be equally effective in harnessing parallelism in logic programs. We also
introduce the late binding mechanism introduced to support the LOR parallel
execution model. An important attribute of this model, which we consider as
significant in determining the effectiveness of the scheme, is that it
provides the framework for a completely distributed implementation of the
underlying multiprocessor abstract machine. This in turn provides the highly
desirable scalable property of a parallel implementation.
* This research was supported in part by DARPA research contract MDA903-86-
~~C-8012 and in part by Texas Adv. Tech. Program contract 3128 (1988).
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
88-CSE-21. ($1.00)
PRELIMINARY EVALUATION OF A STREAM BASED DATA-DRIVEN MODEL
FOR PARALLEL EXECUTION OF LOGIC PROGRAMS
Prasenjit Biswas and Chien-Chao Tseng
March 1988 (Supersedes TR 86-CSE-19)
In this report, we propose a dataflow execution model for parallel logic
programs. The logic programs considered are unannotated (i.e., without mode
declarations, read-only annotations or other control pragmas). This version
of the model supports OR parallel, AND pipelined execution. Eager evaluation
is supported by managing the binding environment using a non-strict structure
S-stream (stream of streams). One of the major problems of implementing
OR-parallelism is related to efficient management of multiple binding
environments. The multilevel stream structure provides an effective solution
to the problem. The simulation results of an implementation of the execution
model on an abstract tagged-token dynamic dataflow are presented. In the
simulation we consider multiple matching units, multiple structure memories
and multiple stream tables.
-----------------------------------------------------------------------------
88-CSE-23. ($4.00)
AN ASSEMBLY LANGUAGE COURSE USING SINGLE-STEP CUMULATIVE TEACHING TECHNIQUE
Sonny Maung, Murat M. Tanik, Behrooz Shirazi
March 1988
The objective of this course is to demonstrate engineering students
general methods of assembly language program development using a
state-of-the-art implementation of Assembly Language (Microsoft Assembler) as
a laboratory environment and the 8086 assembly language itself as a medium of
expression. In this course we used Microsoft Assembler as our laboratory
tool. In our treatment of the language elements we use Single-Step
Cumulative (SSC) technique of teaching that we also used in our Pascal text
(Advanced Turbo Pascal Techniques, Jan. 1988, published by Wordware Inc.
Plano, TX, 75074).
-----------------------------------------------------------------------------
88-CSE-24. ($1.00)
A FORMAL DEFINITION OF THE
INTERACTION STRUCTURE OF COMMUNICATING SEQUENTIAL PROCESSES
Sonny Maung, Murat M. Tanik, Karl Durre
March 1988
The Communicating Sequential Processes is used as a computing model to
define and study parallel systems. The structural similarity between the CSP
models and Petri Net models can be exploited to construct, at a higher
granularity, a structured model for a system of interacting processes. An
observer process can be defined as one of the communicating sequential
processes, thus bringing the observer and the observed system under the same
formalism. This approach lends itself to applications in discrete event
simulation and, potentially, in parallel program debugging.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
88-CSE-25. ($12.50)
A LABORATORY-ORIENTED BASIC PROGRAMMING COURSE FOR ENGINEERING STUDENTS
Udo W. Pooch Murat M. Tanik
Texas A&M University Southern Methodist University
April 1988
The objective of this courseware is to demonstrate engineering students
general methods of program development using a state-of-the-art
implementation of BASIC language (QuickBasic) as a laboratory environment and
the BASIC language itself as a medium of expression. One reason for the
popularity of BASIC in an age when reliable, relatively inexpensive implemen-
tations of FORTRAN, Pascal, Modula-2, LISP, Prolog, even Ada (we have
developed a Computer Based Courseware in Ada as well -- SMU TR 88-CSE-16)
available is the existence of a large collection of BASIC programs in various
areas of science and engineering. Another is the fact that BASIC is readily
available on every PC and easy to learn and, consequently, has a large
following among scientists, engineers, statisticians, and general PC users.
In addition, recent introductions of BASIC implementations with very
practical, functional and attractive integrated environments such as
Microsoft QuickBasic, TurboBasic, TrueBasic and others provide a bottom-line
prototyping system for the BASIC followers.
In this courseware we use Microsoft QuickBasic as our laboratory proto-
typing tool. In our treatment of the language elements we use Single-Step
Cumulative (SSC) technique of teaching that we also used in our Pascal text
(Advanced Turbo Pascal Techniques, Jan. 1988, published by Wordware Inc.
Plano, TX 75074). In project developments we employ the rapid protoktyping
methodology.
-----------------------------------------------------------------------------
88-CSE-26. ($1.00)
CR: A CONSTRAINED RESOURCE PLANNING MODEL*
D. Y. Y. Yun and N. P. Keng
April 1988
This paper presents a new planning model for constrained resource (CR)
planning problems, in which the amount of available resource is limited and
usually monotonically diminishing as the planning process progresses. The
subgoals are tightly-coupled since they compete for the limited resources.
Under these circumstances, the traditional least commitment planning strategy
is necessarily to be divided into two separate policies, according to subgoal
priority and subplan impact. These two policies -- graceful retreat and
least impact -- help to make this CR planning approach sensitive to dynamic
interactions among subgoals. Graceful retreat policy selects a subgoal
dynamically according to their criticality. Least impact policy dynamically
chooses a subplan for the selected subgoal according to the cruciality of
each subplan, which expresses the impact on the rest of the unachieved
subgoals. The CR planning model has been successfully applied to several CR
planning problems.
*~This research was supported in part by the DARPA under contract
~~MDA903-86-C-0182.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
88-CSE-27. ($1.00)
INTERACTION-SENSITIVE PLANNING SYSTEM FOR JOB-SHOP SCHEDULING*
N. P. Keng, D. Y. Y. Yun, M. Rossi
April 1988
This paper presents a planning system for the job-shop scheduling
problem. The system adopts an operand-based perspective of the problem
decomposition which decomposes the original problem into a set of operation
subproblems. Two heuristics -- graceful retreat and least impact -- that are
sensitive to dynamic interactions between operations are used to guide the
search. Graceful retreat orders operations by their criticality and selects
the most critical operation as the next task. Least impact orders time
intervals by their cruciality and selects the least crucial one to commit to
operation. The design of the system is described in detail and the
flexibility of the system is discussed.
*~This research was supported in part by the DARPA under contract
~~MDA903-86-C-0182.
-----------------------------------------------------------------------------
88-CSE-28. ($1.25)
THE OBJECT ORIENTED DATA MODEL DEFINED*
Francisco Mariategui, Margaret H. Eich, Sohail Rafiqi
April 1988
Much research has recently been performed in the area of Object Oriented
Data Bases (OODB). However, there is little consensus among researchers as
to the actual definition of an OODB. Indeed there are probably as many
definitions of the OODB concept as there are people interested in it. To
guarantee the proper development of the OODB paradigm, to facilitate
discussions and understanding, and to provide some degree of consistency
among OODB implementations, we feel that an Object Oriented Data Model (OODM)
definition is crucial. In this paper we provide an initial definition for an
OODM.
*~This work was partially supported by NSF Grant IRI-8713654.
-----------------------------------------------------------------------------
88-CSE-29. ($1.00)
ON GENERALIZATIONS IN NETWORKING SOFTWARE TO ENCOURAGE CODE PORTABILITY
Patrick Peters Roy Dcruz, Chiun-Teh Sung, Christine Wang,
Texas Instruments Branislav Meandzija -- Southern Methodist University
July 1988
Networking software is highly dependent on hardware and operating system
features and therefore difficult to port in an heterogeneous environment.
The variety of issues ranges from different byte orderings of a machine word
to different access to communication hardware and/or user equipment.
We discuss the principal issues involved in porting networking software
and report on solutions that have been used to implement a standard
environment interface to encourage code portability. This interface has been
designed to provide a uniform environment to protocol drivers generated by
the Archetype language compiler. We outline the structure of our
implementation and elaborate on issues relating to the environment interface.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
88-CSE-30. ($1.00)
SPARSEST CUTS AND BOTTLENECKS IN GRAPHS*
David W. Matula Farhad Shahrokhi
Southern Methodist University New Mexico Inst of Mining and Technology
September 1987 (Revised September 1988)
The problem of determining a sparsest cut in a graph is characterized
and its computation shown to be NP-hard. A class of sparsest cuts, termed
bottlenecks, is characterized by a dual relation to a particular polynomial
time computable multicommodity flow problem. Efficient computational
techniques for determining bottlenecks in a broad class of instances are
presented.
*~This report is to appear in the Journal of Discrete Applied Mathematics.
-----------------------------------------------------------------------------
88-CSE-31. ($1.00)
ABSTRACT MACHINE LOG Df: REPORT #1*
Prasenjit Biswas and Chien-Chao Tseng
September 1988
The abstract data-driven machine model, named LogDf, is developed for
parallel execution of logic programs. The execution scheme supports
OR-parallelism, Restricted-AND parallelism and stream parallelism. Multiple
binding environments are represented using stream of streams structure
(S-stream). Eager evaluation is performed by passing binding environment
between subgoal literals as S-streams, which are formed using non-strict
constructors. The hierarchical multi-level stream structure provides a
logical framework for distributing the streams to enhance parallelism in
production/consumption as well as control of parallelism. The scheme for
compiling the dataflow graphs eliminates the necessity of any operand
matching unit in the underlying dynamic dataflow architecture. The details
of binding representation and efficient representation for structures/lists
are also included.
*Research was partly supported by a Texas ATP Grant Contract 3128 (1988).
A shorter version of this report appeared in the Proc. of Fifth Gen. Comp.
Syst. Conf., Tokyo, November 1988.
-----------------------------------------------------------------------------
88-CSE-32. ($6.00)
EQUBE Euclidean QUotient Bit Engine Simulator*
Kyle L. Townsend, Paul Bartholomew, Murat M. Tanik, David W. Matula
November 1988
~~~~~We discuss the implementation, operation, and arithmetic foundation of a
simulation environment for an on-line arithmetic unit for bit-pipelined
rational arithmetic, known as the Euclidean Quotient Bit Engine (EQUBE). The
arithmetic unit was designed by David~W.~Matula and Peter~Kornerup. The
simulator uses computer graphics for algorithm visualization to aid in
research and demonstration of the arithmetic unit.
* This research is supported in part by the National Science Foundation under
grant DCR-831529.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
88-CSE-33. ($1.00)
DESIGN AND AUTOMATIC IMPLEMENTATION OF NETWORKING SOFTWARE WITH YANC
Branislav Meandzija*, Chiun-Teh Sung*, Christine Wang*,
Roy Dcruz*, Patrick Peters**
~~~~~Proliferating communications environments and applications need a
multitude of new protocol implementations. One way of speeding up the
process of development of new protocol implementations is by providing
translators for protocol specification languages. Such translators aid the
design, specification, and implementation process by automatically
transforming abstract, implementation independent, protocol specifications
into protocol drivers.
~~~~~We report on the development and usage of Yet Another Network Compiler
(YANC) that translates Archetype executable specifications into C code in
three different system environments. YANC has been used to automatically
generate protocol drivers for the equivalent of ISO OSI layers 2 to 5. It
reduces the number of lines coded (compared to traditional implementation
languages such as C) by a factor of 10 to 20.
~~~~~Index terms - Protocol design and implementation, software development
tools, communications, automatic program generation, protocol specification.
* Southern Methodist University
** Texas Instruments
-----------------------------------------------------------------------------
88-CSE-34. ($1.00)
INTELLIGENT LIFETIME SUPPORT FOR REAL-TIME SYSTEMS
David E. Langworthy and Murat M. Tanik
November 1988
~~~~~Discussing the degrees of automation in Software Engineering Herbert
Simon made the following assertion. "It is not a question of whether we want
to automate more of this [development] process, and since part of the system
we want now to automate is a highly unstructured part of the process, it is
not really a question of whether we want to use artificial intelligence
methods in software engineering: it is a question of whether artificial
intelligence is powerful enough, whether we yet know enough about artificial
intelligence, or whether it is advanced enough to really help us."~~With this
concept in mind we investigated, in this research, possibilities of
automating the design of real-time systems.
-----------------------------------------------------------------------------
88-CSE-35. ($1.25)
MAIN MEMORY DATABASE RESEARCH DIRECTIONS*
Margaret H. Eich
November 1988
~~~~~The state of MMDB research with respect to some of the many unsolved
problems is investigated. For MMDB systems to realize their full performance
potential, the issues raised here must be addressed. We hope that this
discussion will increase interest in main memory systems and stimulate future
research activities.
*~This material is based in part upon work supported by the Texas Advanced
~~Research Program (Advanced Technology Program) under Grant No. 2265 and by
~~the National Science Foundation under Grant No. IRI-8713654.
~~This report appears in Proceedings of the 1989 International Workshop on
~~Database Machines.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
88-CSE-36. ($5.00)
A CRITICAL EXAMINATION OF SEVERAL CONCURRENT PROGRAMMING ENVIRONMENTS
WITH AN OVERVIEW OF THE OCCAM PROGRAMMING LANGUAGE AND A PARALLEL PDE SOLVER
Peter Miller and Murat M. Tanik
November 1988
In this document, we attempt to record some of the experiences of a
nine-month experiment with parallel programming environments. In September
of 1987, the task of exploiting parallelism in algorithms for numerically
solving certain partial differential equations was presented to the authors
as a class project sponsored by the Mobil Oil Corporation. We began the
experiment with the tool of the Occam programming language, in one sequential
implementation of which (Occam-1 running on a VAX) a small mathematical
function interpreter was constructed. After some preliminary research into
parallel architectures and numerical methods, a parallel algorithm was
presented to Mobil in December of 1987. This algorithm solved the diffusion
equation on a Cartesian mesh of independent parallel processors. In January
of 1988, an implementation of this algorithm underwent development within the
Transputers Development System (TDS) compiling Occam-2 code. The target
machine was a Transputer network, with which the speedup associated with the
parallel algorithm could be observed. There was a "learning curve"
associated with this phase of development as well, especially since there was
a minimum of resource material available (including human resources). In
fact, as a result of this lack of information concerning the TDS, certain
problems became effectively unsolvable, and that particular implementation
was abandoned. At this point, an implementation in terms of the more
standard programming language Ada was sought.
-----------------------------------------------------------------------------
88-CSE-37. ($1.75)
HEURISTICS FOR NETWORK ROUTING IN STATIC TASK SCHEDULING
Behrooz Shirazi and Mingfang Wang
December 1988
Accurate static task scheduling on a multiprocessor system requires
precise information about inter task data communication. In a message-
passing, single-stage, n-dimensional network environment, this information
includes the length of communication as well as the current load on the links
on which the communication is to be conducted. Three heuristic-based routing
algorithms are presented in this paper. They take into account the above
factors and attempt to provide the best routes for communication among the
tasks using a static task scheduling scheme. This routing information can
then be used during the run-time to manage the network. Each method can be
used in the static scheduling algorithms to compute the time needed to
transfer messages in a multiprocessor system. The algorithms not only
compute the accurate times that are needed to send messages from multiple
sources to a destination, but also indicate the paths that are used to
transfer the messages. The optimal routing is an NP-complete problem. The
proposed algorithms solve this problem by employing heuristics such as
shortest and least blocking paths.
-----------------------------------------------------------------------------