leff@smu.UUCP (Laurence Leff) (03/01/88)
SOUTHERN METHODIST UNIVERSITY
Computer Science and Engineering Department
Dallas, TX 75275-0122
Technical Reports issued Sept. 1986 - December 1987
The Computer Science and Engineering Department at Southern Methodist University is pleased to announce the availability
of recent Technical Reports. An abstract of each is attached.
Please check the Technical Reports you wish to receive.
Quantitities are limited and will be supplied until copies are exhausted. Please remit cost for each report ordered.
(Checks payable to Southern Methodist University.) There is no charge for those institutions with whom we have a
reciprocal gratis agreement.
Tech
Report
_____ (86-CSE-20) AN ALTERNATIVE TO THE REFERENCE MODEL OF OPEN SYSTEMS INTERCONNECTION (TOWARDS TRULY OPEN SYSTEMS II).
Branislav Meandzija, William P.-C. Ho ($1.25)
_____ (86-CSE-21) ARCHETYPES OF COMPUTER COMMUNICATIONS. Branislav Meandzija ($1.00)
_____ (86-CSE-22) THE REUSE SYSTEM: CATALOGING AND RETRIEVAL OF REUSABLE SOFTWARE. Susan P. Arnold and
Stephen L. Stepoway ($1.25)
_____ (86-CSE-23) DESIGN OF A MMDB DBM. Margaret H. Eich and Arthur James ($1.75)
_____ (86-CSE-25) A BIT-SERIAL ARITHMETIC UNIT FOR RATIONAL ARITHMETIC. David W. Matula and
Peter Kornerup (No cost for IEEE reprint.)
_____ (87-CSE-1) A COMPARATIVE STUDY OF SYNCHRONIZATION MODELS EXPLOITABLE FOR REAL-TIME SOFTWARE DEVELOPMENT
ENVIRONMENT DESIGN AND TESTING. Murat Tanik ($4.00)
_____ (87-CSE-2) THE MANUAL OF THE SWITCHBOX ROUTER. N. P. Keng, W. P.-C. Ho, D.~Y.~Y.~Yun ($1.75)
_____ (87-CSE-3) DERIVING PROTOCOL ARCHITECTURE SPECIFICATIONS FROM FORMALIZED NETWORK APPLICATION SERVICE REQUIREMENTS
AND ENVIRONMENT CONSTRAINTS. Nancy~Hayward and Branislav Meandzija ($1.25)
_____ (87-CSE-4) THE MAXIMUM CONCURRENT FLOW PROBLEM. Farhad Shahrokhi and David~W.~Matula ($1.25)
_____ (87-CSE-5) AN ABSTRACT MACHINE MODEL TO SUPPORT LIMITED-OR(LOR)/RESTRICTED-AND PARALLELISM(RAP) IN LOGIC
PROGRAMS. Prasenjit Biswas and Shyh-Chang Su ($1.50)
_____ (87-CSE-6) COMPARING MMDB SYSTEMS. Margaret H. Eich ($1.00)
_____ (87-CSE-7) A PARALLEL ARCHITECTURE MODEL SUPPORTING DATABASE OPERATIONS. Behrooz~Shirazi ($1.25)
_____ (87-CSE-8) PARALLEL RENDERING OF FRACTAL SURFACES. Stephen L. Stepoway and Michael~Christiansen ($1.25)
_____ (87-CSE-9) AN ANNOTATED BIBLIOGRAPHY ON SOFTWARE METRICS. Murat M. Tanik ($1.25)
_____ (87-CSE-10) PREDICTION MODELS FOR SOFTWARE METRICS. Murat M. Tanik ($1.25)
_____ (87-CSE-11) REUSABILITY AND CONCURRENCY ISSUES IN THE REAL-TIME USE OF Ada*.
W.~P.~Yin, P.~H.~Liou, M. M. Tanik ($1.75)
_____ (87-CSE-12) FROM PASCAL & C TO C++: A CRITICAL REVIEW, A NEW SYSTEM DESIGN PARADIGM, AND CASE STUDIES.
M. G. Christiansen and M. M. Tanik ($2.50)
_____ (87-CSE-13) OBJECTIVE LINDA: AN OBJECT-CENTERED PERSPECTIVE OF LINDA CONCEPTS, AND ISSUES OF IMPLEMENTATION.
Michael G. Christiansen, Murat M. Tanik, Stephen L. Stepoway ($2.00)
_____ (87-CSE-14) TRANSACTION SKELETONS: TOOLS FOR DATABASE SIMULATIONS. Margaret H. Eich ($1.25)
_____ (87-CSE-15) A HYPERCUBE-BASED DATAFLOW MACHINE. Behrooz Shirazi ($1.00)
_____ (87-CSE-16) DETERMINING EDGE CONNECTIVITY IN O(nm). David W. Matula (No charge for reprint.)
_____ (87-CSE-17) AN AGENT FOR INTELLIGENT MODEL MANAGEMENT.
John I. C. Liu, David Y. Y. Yun, Gary Klein ($1.50)
_____ (87-CSE-18) A GRAPHICS ORIENTED DESIGN METHODOLOGY FOR REAL TIME CONTROL SYSTEMS USING ADA.
Geoffrey C. Hingle, Steven L. Gilbert, Murat M. Tanik ($1.00)
_____ (87-CSE-19) ANALYSIS OF AUTOMATIC DEBUGGING AND AN AUTOMATIC DEBUGGING EXPERIMENT.
David E. Langworthy, David Y. Y. Yun, Murat M. Tanik ($1.00)
_____ (87-CSE-20) VLSI DESIGN OF A SIGNAL PROCESSING CHIP.
Behrooz Shirazi and Pradipto Mukherjee ($1.75)
_____ (87-CSE-21) PERFORMANCE ANALYSIS OF MARS LOGGING, CHECKPOINTING, AND RECOVERY.
Chinfeng Fan and Margaret H. Eich ($1.00)
_____ (87-CSE-22) A FUZZY HYBRID MODEL FOR PATTERN CLASSIFICATION. Prasenjit Biswas ($1.25)
_____ (87-CSE-23) INFERENCE OF MINIMAL DFA FROM FINITE SAMPLE: A FORMAL POWER SERIES APPROACH.
Prasenjit Biswas ($1.00)
_____ (87-CSE-24) SOFTWARE ENGINEERING ACTIVITY AREAS AND TOOLS: A CORRESPONDENCE.
M. M. Tanik and Udo W. Pooch ($1.00)
_____ (87-CSE-25) A PARTIALLY ANNOTATED BIBLIOGRAPHY ON CRYPTOGRAPHY. Murat M. Tanik ($1.00)
_____ (87-CSE-26) TOPICS IN STATIC DATA COLLECTION AND PROGRAM COMPLEXITY. Murat M. Tanik ($2.75)
_____ (87-CSE-27) A PREDICATE/TRANSITION NET MODEL OF TRANSPORT LAYER CLASS 1 PROTOCOL ENTITY.
Sonny Maung and Branislav Meandzija ($1.25)
_____ (87-CSE-28) EVALUATION OF THREE HEURISTIC FUNCTIONS FOR TASK ALLOCATION.
Behrooz Shirazi and Mingfang Wang ($1.00)
*Ada is a registered trade mark of the U.S. government, Ada Joint Program Office.
Mailing Address: (if different than listed)
________________________________________________________
________________________________________________________
________________________________________________________
________________________________________________________
-----------------------------------------------------------------------------
86-CSE-20. ($1.25)
AN ALTERNATIVE TO THE REFERENCE MODEL OF OPEN SYSTEMS INTERCONNECTION
(TOWARDS TRULY OPEN SYSTEMS II)
Branislav Meandzija and William P.-C. Ho
October 1986
Several years ago the International Organization for Standardization
(ISO) introduced in its Reference Model for Open Systems Interconnection
(OSI) the idea of implementing interaction between independent systems by
designing these systems to be open. This approach is based on establishing
communications rules by defining a conventional protocol architecture. We
introduce 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. The former approach is
specific to existing communications technologies and purposes, while the
latter minimizes such assumptions, providing a more flexible communications
standard. Instead of proposing concrete communication rules, we define a
model for the representation of knowledge about software communication
technologies, and an inference mechanism for the deduction of protocol
architectures from this knowledge. We use sets of predicate functions to
represent knowledge of networking entities about communications tasks and
technologies. We then define the deduction of specifications of particular
technologies by means of functions that logically combine these predicate
function sets. We illustrate our approach by defining sample functions.
-----------------------------------------------------------------------------
86-CSE-21. ($1.00)
ARCHETYPES OF COMPUTER COMMUNICATIONS
Branislav Meandzija
October 1986
An archetype of computer communications is a denotation of a computer
communications technology. This denotation is composed out of denotations of
well-known constant concepts of computer communications. A specification of
a~distributed-system architecture by means of archetypes amounts to
specifying the scoping relation between the archetypes specified. Since this
specification is entirely descriptive and free of any operational details, it
is trivially writable, understandable, and modifiable.
Archetype is a method that not only defines a specification language
based on archetypes but also a corresponding execution model and the
transformation from descriptive into executable specifications. In this
article we introduce the concept of archetypes as it's used in the
specification framework of Archetype.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
86-CSE-22. ($1.25)
THE REUSE SYSTEM: CATALOGING AND RETRIEVAL OF REUSABLE SOFTWARE*
Susan P. Arnold
Texas Instruments, Inc.
Stephen L. Stepoway
Southern Methodist University
October 1986
Only a small percentage of software in any given application area is
unique and/or innovative. The remaining generic software could be reused to
reduce the overall cost of producing software. An obstacle in any scheme for
reusing software is that of matching current needs with existing software and
designs. The REUsing Software Efficiently (REUSE) system was defined to help
software engineers catalog and retrieve existing software information.
In keeping with the overall philosophy of the REUSE system, existing
storage and retrieval mechanisms are utilized. The REUSE system provides a
customizable, menu-driven front-end to information retrieval (IR) systems.
A~software organization uses keywords to build a hierarchical system of menus
which reflect their specific standards and methodologies. These menus and
keywords provide consistent classification of contributed software and are
used to construct information retrieval queries. The REUSE system also
maintains a thesaurus to reduce terminology differences within the user
community.
* Condensed version appears in Proc. COMPCON '87.
-----------------------------------------------------------------------------
86-CSE-23. ($1.75)
DESIGN OF A MMDB DBM*
Margaret H. Eich
Arthur James
October 1986
The initial design of a main memory database (MMDB) backend database
machine (DBM) is described. This MAin memory Recoverable database with
Stable log (MARS) is designed to provide quick recovery after transaction,
system, or media failure, and to also provide efficient transaction
processing.
* Revised version appears in Proceedings of the Fifth International Workshop
on Database Machines, pp 468-481.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
86-CSE-25. (No cost for IEEE reprint)
A BIT-SERIAL ARITHMETIC UNIT FOR RATIONAL ARITHMETIC**
Peter Kornerup
Aarhus University
David W. Matula*
Southern Methodist University
December 1986
We describe a binary implementation 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 the binary lexicographic
continued fraction (LCF) representation of the rational operands. The
operands and results are processed in a most-significant-bit first on-line
fashion with bit level logic leading to less delay in the computation cell
when compared to operation on the full partial quotients of the standard
continued fraction representation. Minimization of delay is investigated
with the aim of supporting greater throughput in cascaded parallel
computation with such computation cells.
*This research was supported by the National Science Foundation grant
DCR-8315289.
**Published in Proc. IEEE Eighth Sym. Comp. Arith., 1987, 204-211.
-----------------------------------------------------------------------------
87-CSE-1. ($4.00)
A COMPARATIVE STUDY OF SYNCHRONIZATION MODELS EXPLOITABLE FOR
REAL-TIME SOFTWARE DEVELOPMENT ENVIRONMENT DESIGN AND TESTING
Murat M. Tanik
January 1987
A survey of synchronization models are presented. These models are Task
Systems model, Routed Network model, Petri nets, general resource systems,
vector addition systems, etc. Relationship among models are given. Examples
provided.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
87-CSE-2. ($1.75)
THE MANUAL OF THE SWITCHBOX ROUTER
N. P. Keng, W. P.-C. Ho, D. Y. Y. Yun
January 1987
Switchbox routing can be viewed as a planning problem in which the
overall goal is to connect net terminals. This goal can be decomposed into a
set of subgoals. Each subgoal is to connect a pair of terminals. These
subgoals may be conjuncted or disjuncted and compete for limited resources,
i.e. tracks. The router uses a least commitment strategy composed of two
policies called "graceful retreat" and "least impact". Each of them is
composed of a set of subpolicies. Graceful retreat selects the subgoal
currently judged most "critical" as the subgoal to achieve next. Least
impact selects a subplan, i.e. a path, currently judged to use resources
least "crucial" to the remaining subgoals. The chronological backtracking
approach is used to retract the wrong decision made earlier.
-----------------------------------------------------------------------------
87-CSE-3. ($1.25)
DERIVING PROTOCOL ARCHITECTURE SPECIFICATIONS FROM FORMALIZED NETWORK
APPLICATION SERVICE REQUIREMENTS AND ENVIRONMENT CONSTRAINTS
Nancy Hayward
E-Systems Inc., Garland, TX
Branislav Meandzija
Southern Methodist University
January 1987
In this article we introduce a method for deriving protocol architecture
specifications from network application specifications. First we develop a
language which formalizes network application service requirements and
environment constraints. Then we define the relationship between these
formalized applications and protocol architectures by rules which map
specific combinations of service requirements and environment constraints to
classes of protocol architectures. We assume Archetype as the protocol
architectures specification technique. Classes of protocol architecture
specifications are represented as predicates on the syntactic domains of
Archetype. Therefore, the end result of the derivation process is a
constraint satisfied specification of Archetype that defines the set of
protocol architectures appropriate for the specified network application.
Such specifications can be used for the design and run-time specification and
implementation of protocol architectures.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
87-CSE-4. ($1.25)
THE MAXIMUM CONCURRENT FLOW PROBLEM
Farhad Shahrokhi and David W. Matula
February 1987
The maximum concurrent flow problem (MCFP) is a multicommodity flow
problem where every pair of entities can send and receive flow concurrently.
The ratio of the flow supplied between a pair of entities to the predefined
demand for that pair is termed throughput and must be the same for all pairs
of entities for a concurrent flow. The MCFP objective is to maximize the
throughput, subject to the capacity constraints. We develop a fully
polynomial time approximation scheme for the MCFP for the case of arbitrary
demands and uniform capacity. Computational results are presented. We show
that the problem of associating costs (distances) to the edges so as to
maximize the minimum cost of routing the concurrent flow is the dual of the
MCFP. We also derive a path-cut type duality theorem to expose the
combinatorial structure of the MCFP. Our duality theorems are proved
constructively for arbitrary demands and uniform capacity using the
algorithm. Applications include packet switched networks and cluster
analysis.
-----------------------------------------------------------------------------
87-CSE-5. ($1.50)
AN ABSTRACT MACHINE MODEL TO SUPPORT LIMITED-OR(LOR)/
RESTRICTED-AND PARALLELISM(RAP) IN LOGIC PROGRAMS*
Prasenjit Biswas and Shyh-Chang Su
February 1987
In this report we present an abstract multiprocessor machine model for
parallel execution of Logic Programs. To support a message-passing
implementation (without any shared global memory), we have developed a new
execution mechanism based on the concepts of late binding and selective
copying of uninstantiated variables across activation frames. It will be
shown that the demand-driven OR-parallel execution scheme, introduced in this
report, in combination with Restricted-AND parallel execution provides a
convenient framework for harnessing combinatorially explosive parallelism in
non-annotated Logic Programs. The abstract operation set architecture of a
processing element in the multiprocessor model is also included.
*This research was supported in part by Dept. of Defense Darpa Research
Contract MDA903-86-C-0182, 1986.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
87-CSE-6. ($1.00)
COMPARING MMDB SYSTEMS
Margaret H. Eich
February 1987
The processing requirements of a MAin memory Recoverable database with
Stable log (MARS) is compared to that of HALO and MM-DBMS. A simple analytic
performance analysis shows that MARS performs better than MM-DBMS.
-----------------------------------------------------------------------------
87-CSE-7. ($1.25)
A PARALLEL ARCHITECTURE MODEL SUPPORTING DATAFLOW OPERATIONS*
Behrooz Shirazi
February 1987
The data driven architecture has been widely proposed in the literature
as an alternative to the von-Neumann design to handle the real time and 5th
generation applications [1,2]. However, the network delays at the fine-grain
dataflow level and handling of large arrays are some of the problems which
should be addressed in these architectures. In this paper, we introduce a
new model for dataflow computation which yields itself to an efficient
realization of both static and dynamic dataflow architectures. Furthermore,
the proposed model provides grounds for efficient handling of arrays in an
SIMD fashion. Some implementation issues, the VLSI constraints, and
architectural support for the model are discussed. The proposed organization
achieves parallelism at the program block level (large-grain parallelism),
instruction level (fine-grain parallelism), and data level (array
processing). The system behavior is studied through a probabilistic
simulation model and the conclusions are presented.
* Appears in NCC '87, pp 119-126.
-----------------------------------------------------------------------------
87-CSE-8. ($1.25)
PARALLEL RENDERING OF FRACTAL SURFACES*
Stephen L. Stepoway and Michael Christiansen
March 1987
Fractal surfaces have been shown to be a useful modeling technique for
terrain in computer graphics. Although an algorithm has been developed for
ray tracing (Mandelbrot) fractal surfaces, the technique is computationally
very expensive. The large degree of parallelism inherent in the problem
suggests the use of parallel architectures for generating these images. We
describe a parallel rendering algorithm for shared memory MIMD machines which
takes advantage of image coherence to reduce computation. This algorithm
has, on a Sequent Balance 21000 with 20 processors, demonstrated a
near-linear speedup. We examine the possible synchronization bottlenecks via
two variants of the parallel algorithm.
*This work was supported in part by DARPA under contract MDA903-86-C-0182.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
87-CSE-9. ($1.25)
AN ANNOTATED BIBLIOGRAPHY ON SOFTWARE METRICS
Murat M. Tanik
February 1987
This bibliography includes a set of Abstracts together with a short
comment for each of the selected papers.
-----------------------------------------------------------------------------
87-CSE-10. ($1.25)
PREDICTION MODELS FOR SOFTWARE METRICS
Murat M. Tanik
May 1987
Data collected from a set of COBOL and FORTRAN programs as well as from
questionnaires are used in the development of a set of program complexity
models using multiple linear regression. For all of the models developed,
high R-square values are observed. The experiment contributes to the
accumulating evidence that the programmer's guess of the program complexity
is related to measurable program characteristics and it might play an
important role in program development. For more definitive results, the
repetition of the experiment is suggested.
-----------------------------------------------------------------------------
87-CSE-11. ($1.75)
REUSABILITY AND CONCURRENCY ISSUES IN THE REAL-TIME USE OF Ada*
W. P. Yin, P. H. Liou, M. M. Tanik
May 1987
This paper will present our explorative work in software reusability and
concurrent programming. This work was divided into two parts. First, in
order to abstract the reusable components, three application problems were
tried to be solved by means of object-oriented programming using Ada.
Second, in order to address how Ada provides an environment for concurrent
programming, several concurrent programming concepts were described using
Ada.
*~Ada is a registered trade mark of the U.S. government, Ada Joint Program
~Office.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
87-CSE-12. ($2.50)
FROM PASCAL & C TO C++: A CRITICAL REVIEW,
A NEW SYSTEM DESIGN PARADIGM, AND CASE STUDIES
M. G. Christiansen and M. M. Tanik
May 1987
This report will introduce the reader to C++, a programming language.
Since C++ is an extension of C, we include a review of C before introducing
C++. For the sake of completeness, a concise comparison of Pascal and C is
presented. It is hoped that this will provide a uniformity for readers
familiar with either Pascal or C.
We begin with the C/Pascal comparison, followed by a critical review of
C++. We then present a discussion of a new object centered systems design
paradigm. Finally we present two case studies that demonstrate the pertinent
C++ features in greater detail.
-----------------------------------------------------------------------------
87-CSE-13. ($2.00)
OBJECTIVE LINDA: AN OBJECT-CENTERED PERSPECTIVE OF LINDA CONCEPTS,
AND ISSUES OF IMPLEMENTATION
Michael G. Christiansen, Murat M. Tanik, Stephen L. Stepoway
June 1987
This is a description of distributed programming system which is based
on the Linda concepts [1,2]. This work describes a method of implementing a
name space shared by a network of processors. Our extensions allow an object
oriented approach to defining the items stored in the distributed name space
and methods that operate on them.
This report describes how these ideas could be implemented in a network
of processing elements. This description includes the network protocol used
to implement the distributed name space.
-----------------------------------------------------------------------------
87-CSE-14. ($1.25)
TRANSACTION SKELETONS: TOOLS FOR DATABASE SIMULATIONS
Margaret H. Eich
July 1987
A realistic technique to represent database transactions, transaction
skeletons, when performing database system simulations is proposed. Previous
database simulation studies have had an overly abstract view of applications
based on a single transaction, a reference string for transactions, or read
only transactions. These approaches are not satisfactory when trying to
predict database system performance in a multiprocessor or distributed
environment. By providing the ability to define parallelism within
transaction execution at the individual operation level, these skeletons
facilitate execution of more realistic simulation runs.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
87-CSE-15. ($1.00)
A HYPERCUBE-BASED DATAFLOW MACHINE*
Behrooz Shirazi
July 1987
The purpose of this technical report is to address the design issues and
execution model of a proposed dataflow machine. The simulation of the
machine and performance evaluation of the system is currently under
investigation and the results will soon be available. As the name,
Hypercube-Based Dataflow Machine indicates, the proposed organization is
based on applying the dataflow computation model to a Hypercube
multiprocessor. The Hypercube characteristics such as homogeneity of
processing nodes, scalability, and minimal network delays make the system
ideal for any distributed multi-processing environment. In addition, certain
characteristics of dataflow computations allow a natural and promising
mapping of a dataflow execution model onto a Hypercube structure. This
report addresses these characteristics and discusses the architectural design
of the proposed machine.
*This research was supported in part by the DARPA under contract 5-25089-310.
A more advanced version (recent results) to appear in Intl. Conf. on
Supercomputing, Boston, May 1988.
-----------------------------------------------------------------------------
87-CSE-16. (No charge for reprint)
DETERMINING EDGE CONNECTIVITY IN O(nm)*
David W. Matula
July 1987
We describe an algorithm that determines the edge connectivity of an
n-vertex m-edge graph G in O(nm) time. A refinement shows that the question
as to whether a graph is k-edge connected can be determined in O(kn2). For
dense graphs characterized by $m = omega (n sup 2)$, the latter result
implies that determination of whether a graph is k-edge connected for any
fixed k can be accomplished in time linear in input size.
* Published in Proc. IEEE 28th Sym. FOCS, 1987, 249-251.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
87-CSE-17. ($1.50)
AN AGENT FOR INTELLIGENT MODEL MANAGEMENT*
John I. C. Liu and David Y. Y. Yun
Department of Computer Science and Engineering
Gary Klein
Department of Management Information Sciences
August 1987
Decision Support System (DSS) in management science and Expert System
(ES) in computer science are both aimed at improving decision-making.
However, the current DSS usually concentrate on quantitative model methods
while the ES emphasizes logical expression and reasoning. In this paper,
comparisons of DSS and ES are explored, and ideas of integrating DSS and ES
are presented. It is concluded that the most fruitful area of
cross-fertilization is an extension of expert system technology to apply
models within a DSS. Such an enhanced system will serve as an intelligent
agent between the DSS and the user. Our current research concerns developing
the paradigm for an intelligent agent model to serve as a consultant to help
the user formulate models for achieving a goal.
* Annual National Conf. on Ada Tech., Arlington, VA, March 14-17, 1988.
An early version was also presented in CASE '87, Cambridge, MA, May, 1987.
-----------------------------------------------------------------------------
87-CSE-18. ($1.00)
A GRAPHICS ORIENTED DESIGN METHODOLOGY FOR
REAL TIME CONTROL SYSTEMS USING ADA
Geoffrey C. Hingle, Steven L. Gilbert, Murat M. Tanik
September 1987
Current graphical system design methodologies do not support
documentation of real-time system level design decisions such as the rate of
data computation and the rate of inter-subsystem transmission. We suggest
extensions to a popular existing graphics notation for the Ada programming
language (Buhr diagrams [1]), and demonstrate our notation's ability to
clearly document data calculation and transmission rates. In addition, we
extend the Buhr diagrams to include an Ada data dictionary that documents the
structure of the interface between two objects. The format of the data
dictionary lends itself to subsystem interface definition and coordination,
which in large systems can involve more than one corporation. Two examples
are included, the first models a cruise control system using an original Buhr
diagram, and the second models a hypothetical radar detection system using
our extended notation.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
87-CSE-19. ($1.00)
ANALYSIS OF AUTOMATIC DEBUGGING AND AN AUTOMATIC DEBUGGING EXPERIMENT*
David E. Langworthy, David Y. Y. Yun, Murat M. Tanik
September 1987
An automatic debugging system would significantly reduce the effort
needed to write programs. We developed such a system is available for small
laboratory applications. We are currently exploring the advantages obtained
in the laboratory and their applicability to the area of real-time
programming.
* Presented at CASE '87 Cambridge, MA, May 1987.
-----------------------------------------------------------------------------
87-CSE-20. ($1.75)
VLSI DESIGN OF A SIGNAL PROCESSING CHIP*
Behrooz Shirazi and Pradipto Mukherjee
September 1987
In this paper we address the VLSI layout design of a chip used in a
systolic array for convolution operation. The chip has two major portions
consisting of a multiplier and an accumulator. Each section itself is
pipelined, resulting in a two-level pipeline design. The multiplier views
the operation as a LOGICAL one, without using addition or counting. Such a
novel view provides grounds for a high pipeline throughput. The addition is
almost free of cost since it only extends the multiplier pipeline stages by
two stages, with a negligible area requirement. We discuss the cell design,
cell placement, and a routing scheme in the VLSI layout of the proposed cells
using cMOS technology. In addition, we compare our multiplier against a
number of recently proposed systolic multipliers, using multiplication delay
as the comparison measure. This study shows that the proposed design
outperforms most of the existing schemes for different multiplication sizes.
* This research is supported in part by the DARPA under Contract 5-25089-310.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
87-CSE-21. ($1.00)
PERFORMANCE ANALYSIS OF MARS LOGGING, CHECKPOINTING, AND RECOVERY*
Chinfeng Fan and Margaret H. Eich
October 1987
We report on the results of analytical performance analysis used to
compare MARS and MM-DBMS. With equal numbers and sizes of log records, MARS
supports a higher transaction throughput rate than does MM-DBMS. Even with
larger numbers of log records, obtaining the rate of 1500 transactions
persecond can be supported by MARS logging. The MARS checkpointing rates are
comparable to those of MM-DBMS. In all situations, MARS recovery outperforms
MM-DBMS.
*This work was partially supported by NSF Grant IRI-8713654.
-----------------------------------------------------------------------------
87-CSE-22. ($1.25)
A FUZZY HYBRID MODEL FOR PATTERN CLASSIFICATION*
Prasenjit Biswas
October 1987
In this report we propose a hybrid model for pattern classification.
The model is hybrid in the sense that the first phase of the classifier uses
a~ supervised learning algorithm for establishing the fuzzy separability of
pattern classes based on the Fuzzy set theoretic approach producing
hierarchical binary decision trees; and the second phase uses a syntactic
approach. The effectiveness of the model is demonstrated by using it for
recognition of handprinted Devanagri characters. The principle of classifier
design described in this report establishes a methodology for identifying the
boundary of transition from the geometric to the structural approach in such
hybrid classification schemes.
* To appear in Proc. of Int. Conf. on Pattern Recognition, Cambridge,
England, March 1987 (also Lecture Notes in Computer Science ("Pattern
Recognition 88"), Springer-Verlag).
-----------------------------------------------------------------------------
87-CSE-23. ($1.00)
INFERENCE OF MINIMAL DFA FROM FINITE SAMPLE:
A FORMAL POWER SERIES APPROACH
Prasenjit Biswas
October 1987
An algorithm is proposed for inferring a minimal Deterministic Finite
state automaton through extensions of results of Fliess and Schutzenberger on
equivalence of Recognizable and Rational Formal Power series. The technique
for synthesis of the minimal automaton from a given finite sample of finite
strings is demonstrated. The proposed algorithm could be extended to infer
recursive regular grammars for set of strings of the form uvkw (k>>1). Few
fundamental theorems in Automata theoretic aspects of Formal Power series are
presented as they are not very well known in the literature on Syntactic
Pattern recognition and Grammatical inference.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
87-CSE-24. ($1.00)
SOFTWARE ENGINEERING ACTIVITY AREAS AND TOOLS: A CORRESPONDENCE*
M. M. Tanik - SMU
Udo W. Pooch - Texas A&M
October 1987
Software engineering deals with the problems of producing quality
software. It is documented in the literature that the development of
reliable software systems is an extremely complex task involving the social
dynamics of the personnel, programming skills, and large amounts of money.
The term "software engineering" has different connotations for different user
groups. Our view is to consider software engineering as an example of
"technology transfer" and apply the principles of engineering to the
construction of reliable and economical software. This particular view of
software engineering leads to a taxonomy in terms of software tools
incorporated in a particular software engineering activity area. Thus, the
software engineering activity areas can be classified into four functionally
different groups: 1. Planning tools, 2. Developmental tools, 3. Quality
judgement/control tools, and 4. Operations/maintenance tools.
The remaining sections of the paper introduces the tools used in
planning, development, quality judgement, and maintenance of software
products and their correspondence with software engineering activity areas.
In addition two new software tools, development and complexity graphs, are
briefly reviewed.
* Presented at CASE '87, Cambridge, MA, May 1987.
-----------------------------------------------------------------------------
87-CSE-25. ($1.00)
A PARTIALLY ANNOTATED BIBLIOGRAPHY ON CRYPTOGRAPHY
Murat M. Tanik
October 1987
-----------------------------------------------------------------------------
87-CSE-26. ($2.25)
TOPICS IN STATIC DATA COLLECTION AND PROGRAM COMPLEXITY
Murat M. Tanik
November 1987
The report includes:
1. Software Development Monitoring Graphs
2. A Comparison of Program Complexity Prediction Models
3. Prediction Models for Cyclomatic Complexity
4. A Comparison of Two Different Program Complexity Measures
5. Static Data Collection from COBOL and FORTRAN Programs
6. Two Experiments on a Program Complexity Perception by Programmers.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
87-CSE-27. ($1.25)
A PREDICATE/TRANSITION NET MODEL OF TRANSPORT LAYER CLASS 1 PROTOCOL
Sonny Maung and Branislav Meandzija
December 1987
Within the scope of the Reference Model of Open System Interconnection
the ISO has defined the standard for end-to-end communication by means of the
Transport protocol classes 0-4. The complexity of those protocols calls for
the use of formal techniques for their specification and analysis. We show
how the class 1 transport protocol can be modeled using Predicate/Transition
Nets. The usual Predicate/Transition Net is extended by allowing informal
denotations to describe the action associated with transitions, and by
allowing epsilon condition tests on places. We model the four functions of
the protocol, namely Connection Management, Data Packaging and Transfer,
Error Recovery, and Exception Handling functions, separately.
-----------------------------------------------------------------------------
87-CSE-28. ($1.00)
EVALUATION OF THREE HEURISTIC FUNCTIONS FOR TASK ALLOCATION*
Behrooz Shirazi and Ming-Fang Wang
December 1987
Optimal task scheduling in a multiprocessor environment is known to be
an NP-hard problem. Thus, the research efforts in this area have focused on
heuristic methods for efficient distribution of tasks. This paper introduces
two new static task scheduling algorithms. The first algorithm, called Heavy
Node First (HNF), is very simple and based on a local analysis of program
graph nodes at each level. The second method, called Weighted Length (WL),
considers a more global view of the program graph, taking into account the
relationship among the nodes at different levels. The two schemes are
compared against the classical Critical Path Method (CP/M). For a given
Directed Acyclic Graph (DAG) of n nodes representing a program, it is shown
that HNF requires O(n log(n)) steps while WL and CP/M require O(n2) steps to
accomplish the allocation. The worst case performance of the three
algorithms is analytically evaluated and their average case performance is
evaluated through a simulation study. Considering the program execution time
and the processor(s) idle time as our performance measures, it is shown that
WL outperforms the other methods while CP/M is superior to HNF.
* This research is supported in part by the DARPA under Contract 5-25089-310.
-----------------------------------------------------------------------------