E1AR0002@SMUVM1.BITNET (02/14/86)
1985 TECHNICAL REPORTS
(4th Quarter: October-December)
UCLA COMPUTER SCIENCE DEPARTMENT
University of California
3713 Boelter Hall
Los Angeles, CA 90024
USA
******************************
AN EXPLANATION OF AND CURE FOR MINIMAX PATHOLOGY Bruce Abramson
CSD-850034 $1.50
The minimax procedure has long been the standard method of evaluating nodes
in game trees. The general assumption underlying its use in game-playing
programs is that increasing search depth improves play. Recent work has
shown that this assumption is not always valid; for a large class of games
and evaluation functions, searching deeper decreases the probability of
making a correct move. This phenomenon is called game tree pathology.
Two structural properites of game trees have been suggested as causes of
pathology: independence among the values of sibling nodes, and uniform
depth of wins and losses. This paper examines the relationship between un-
iform win depth and pathology from two angles. First, it proves mathemati-
cally that as search deepens, an evaluation function that does not .ul ask
whether wins can be forced from mid-game positions becomes decreasingly
likely to choose forced wins. Second, it experimentally illustrates the
connection between recognition of mid-game wins and pathological behavior.
Two evaluation functions, which differ only in their ability to recognize
wins in mid-game, are run on a series of games. Despite recognizing fewer
mid-game wins than the theoretically predicted minimum needed to avoid
pathology, the function that checked for them cleared up the pathological
behavior of the one that did not.
The analytic and empirical aspects of this paper combine to form one major
result: As search deepens, so does the probability that failing to check
for forced wins will change the game's outcome. This strengthens the hy-
pothesis that uniform win depth is the cause of pathology.
******************************
DISTRIBUTED COMPUTER SIMULATION OF DATA COMMUNICATION NETWORKS;
PROJECT REPORT III
Shung Cheung, Jack W. Carlyle, Walter Karplus
CSD-850037 $2.50
This is the third in a series of reports on continuing studies of
discrete-event simulation using distributed processing (e.g., on networks
of minicomputers or networks of microcomputer workstations), with applica-
tion to performance prediction for data communication networks. Issues ex-
amined include synchronization mechanism, task allocation algorithms, simu-
lator implementation approaches, and deadlock prevention methods.
******************************
DISTRIBUTED ALGORITHMS FOR ELECTION IN UNIDIRECTIONAL AND COMPLETE NETWORKS
Yehuda Afek
Professor Leonard Kleinrock, Chair
CSD-850036 $8.50
Consider a data communication network of n nodes, each of which has a
unique identifier (id); otherwise the nodes are identical. The nodes are
asleep and have no global information about network topology, number and
ids of other nodes, etc. A distributed election algorithm is a means by
which the nodes of the network distinguish one among them as the leader.
The problem of distributively electing a leader in a network is viewed as a
problem of synchronization among potential candidates for leadership. Each
candidate tries to capture all the nodes. To guarantee that only one
succeeds, all but one candidate are killed. Following this view election
algorithms in a general, two component framework are designed. Component
one is a capturing and termination detection mechanism, assuming only one
candidate. Component two is a synchronization mechanism, to eliminate all
but one candidate.
In arbitrary networks the synchronization is complicated by the uncertain-
ties of nodes about the network topology and the relative location of can-
didates. Two network models are considered: first, a complete network in
which a bidirectional communication link connects every node with every
other, thus eliminating topological uncertainties; and second, the oppo-
site extreme in which topological uncertainties are at maximum -- a strong-
ly connected unidirectional network with some or all links transmitting
messages in one direction only.
The study produces an O(n.log n) messages O (log n) time synchronous and
O(n.log n) messages O(n) time asynchronous election algorithm in complete
networks. For unidirectional networks we derive a distributed election al-
gorithm whose communication complexity is O(n.|E|+n2log n ) bits, where |E|
is the total number of links.
We also establish that OMEGA (n.log n) is a lower bound on the total number
of messages transmitted for achieving election in synchronous complete net-
works. Moreover, it is shown that the time complexity of message-optimal
synchronous algorithms is OMEGA (n.log n ), hence the optimality of our
synchronous complete network algorithm. It remains open whether a sub-
linear time, message-optimal, asynchronous complete network election algo-
rithm exists.
******************************
REDUCED REGISTER SAVING/RESTORING IN SINGLE-WINDOW REGISTER FILES
Toma's Lang and Miquel Huguet
CSD-850040 $1.75
In a register-oriented architecture, the sequence of instructions
corresponding to the function call construct has been identified as consum-
ing a significant fraction of the execution time of typical programs writ-
ten in high-level languages such as C. A large reduction in this time is
obtained by the use of multiple-window register files. However, this ap-
proach has as disadvantages the cost of the large number of registers (in
chips in a MSI/LSI implementation and in area in the VLSI case), the in-
crease in cycle time in a VLSI implementation due to longer data buses, and
the increase of the time for context switching. These disadvantages can be
reduced by the use of multi-size windows and the implementation of the file
as a set of shift registers. However, due to these disadvantages, the
multiple-window approach might not be suitable for all situations. Conse-
quently, it is interesting to develop architectures and compilers that
reduce the cost of function call for the single-window case. In this paper
we present schemes that permit the reduction of the memory traffic due to
register saving and restoring, which is one of the major components of the
execution time of function call/return. We also consider the implementa-
tion of the selected scheme and conclude that the implementation is feasi-
ble and might be a good use of resources to increase execution speed.
******************************
TASK RESPONSE TIME AND MODULE ASSIGNMENT FOR REAL-TIME DISTRIBUTED PROCESSING
SYSTEMS
Kin Kwong Leung
Professor Wesley W. Chu, Chair
CSD-850041 $14.00
Task response time is an important system performance measure for real-time
systems. An analytic model is introduced to estimate task response time
for loosely coupled distributed processing systems with real-time applica-
tions. The model considers such factors as assignment of modules to com-
puters, module precedence relationships, interprocessor communications, in-
terconnection network delay and module scheduling policy. Simulation exper-
iments are used to validate the model assumptions and to show the accuracy
of the model.
The analytic model is first employed to investigate the effects of module
precedence relationships on response times. Our study reveals that the dis-
tributions of module execution times and the mean execution time ratio for
a pair of consecutive modules are major factors for the effects.
The task response time model is then used to study module assignment for
distributed systems. Based on the model, a new local search algorithm for
module assignment is developed. Firstly, each module is assumed to be allo-
cated to a single computer. Task response time is the optimality cri-
terion, and the analytic model becomes the objective function. Search
strategies are established to search for better module assignments. Furth-
er, the algorithm is extended to handle module replications; that is,
modules may be replicated on several computers. The design objective for
replicated module assignment is to minimize task response time with the
thread response time constraints. A new objective criterion which is the
sum of task response time and possible penalty delay to account for the
violations of thread response time constraints is introduced. With this
objective function, not only module copies are optimally assigned to com-
puters, the proper module multiplicities are also iteratively determined by
the algorithm so as to achieve the objective.
The algorithm is validated by applying to two distinct distributed systems
for space defense applications. One system does not require module replica-
tions while the other does. The sub-optimal module assignments generated
by the algorithm provide excellent response time performance on both sys-
tems since the analytic model has considered all major factors that affect
task response time. Therefore, the algorithm can serve as a valuable tool
for distributed systems design.
******************************
HUMAN PROBLEM UNDERSTANDING AND ADVICE GIVING: A COMPUTER MODEL
Alexander Eric Quilici
Professor Michael Dyer, Chair
CSD-850039 $7.75
How are people able to understand someone else's problem and provide them
with advice? How are people able to develop novel solutions to problems
they have never seen before? The thesis presented here is a first step to-
ward answering these questions, presenting a computer model of the process
of problem understanding and advice giving. The problems we consider are
typical planning problems that novice computer users encounter.
We view advice giving as a memory search problem, guided by heuristics for
problem understanding, advice generation, and plan creation. In this
thesis we describe a representational system for user planning problems,
show how advice can be generated using a taxonomy of planning problems and
associated heuristics for advice formulation, present heuristics that can
be used to repair failed plans and to create new plans by combining exist-
ing plans in novel ways, and suggest a memory organization for planning
knowledge that allows for efficient retrieval of relevant planning experi-
ences.
The theory discussed in this thesis is implemented in a computer program
called AQUA (Alex Quilici's UNIX|+ Advisor). AQUA takes natural language
descriptions of problems users are having with the UNIX operating system
and provides natural language advice that explains their failures and sug-
gests solutions. AQUA is also able to create solutions for problems that
it has not been presented with before.
******************************
GRAPHOIDS: A GRAPH-BASED LOGIC FOR REASONING ABOUT RELEVANCE RELATIONS *
Judea Pearl, Azaria Paz
CSD-850038 $1.75
We consider 3-place relations I (x,z,y) where, x,y, and z are three
non-intersecting sets of elements, (e.g., propositions), and I (x,z,y)
stands for the statement: "Knowing z renders x irrelevant to y". We give
sufficient conditions on I for the existence of a (minimal) graph G such
that I (x,z,y) can be validated by testing whether z separates x from y
in G. These conditions define a GRAPHOID.
The theory of graphoids uncovers the axiomatic basis of probabilistic
dependencies and ties it to vertex-separation conditions in graphs. The
defining axioms can also be viewed as inference rules for deducing which
propositions are relevant to each other, given a certain state of
knowledge.
******************************
ANALYSIS OF ALTERNATIVES FOR A SINGULAR VALUE DECOMPOSITION PROCESSOR
Jaime H. Moreno
Professor Tomas Lang, Chair
CSD-850035 $11.75
In this thesis we present an evaluation of different alternatives for the
implementation of a digital system to compute the Singular Value Decomposi-
tion (SVD), in terms of the throughput achievable with a given amount of
hardware. An algorithmic model which captures the properties of the SVD
computation and a methodology for the design of systems exploiting con-
currency are presented and applied to the SVD.
The model uses a directed graph as a description of the algorithm, where
nodes correspond to subcomputations and arcs to precedences among the sub-
functions. Each node is described by its execution time as a function of
the number of operation units used. This model is utilized to evaluate the
cost and performance of implementations with replication, pipelining and
parallelism.
The methodology for the design is essentially an iterative procedure con-
sisting of top-down decomposition and bottom-up refinement of the nodes in
the graph of the algorithm.
It is shown here that, for throughput higher than a certain value which
depends on the computation, a pipelined approach for the implementation of
the SVD algorithm is more attractive than other alternatives currently pro-
posed for such computation. The architecture devised is a multilevel pipe-
lined processor, which exploits concurrency at several levels through
internal pipelines and the use of the parallelism in the subcomputations.
This scheme offers better performance characteristics for a given amount of
hardware than the other alternatives proposed, keeps the realization at a
level of complexity similar to those other alternatives, and is able to
compute the decomposition of matrices of any size without hardware modifi-
cations. However, implementations with the scheme presented exhibit expan-
sibility characteristics such that they can be upgraded if higher
throughput for larger matrices is desired.
The algorithm used is a parallel version of Hestenes' one sided orthogonal-
ization method proposed by Brent et al, which is adapted for implementation
with few processors. The resulting scheme has the same characteristics of
the original one regarding data transfers between units, and it is realiz-
able with any number of parallel processors.
******************************
******************************
Please circle the report(s) you would like to order. ALL REQUESTS MUST BE
PREPAID. Postage has been included for Continental U.S. delivery only.
For foreign delivery please add 15% to cover postage. Foreign
checks/currency WILL NOT be accepted. Checks should be made payable to:
"UCLA COMPUTER SCIENCE DEPARTMENT"
Return this checklist and your check to:
Ms. Brenda Ramsey
UCLA Computer Science Department
School of Engineering & Applied Science
University of California
3731 Boelter Hall
Los Angeles, CA 90024
CSD-850034 $1.00 CSD-850035 $10.75 CSD-850036 $8.25
CSD-850037 $2.00 CSD-850038 $1.50 CSD-850039 $6.75
CSD-850040 $1.50 CSD-850041 $12.25
Please let us know if you would like to have your name REMOVED
or ADDED to our hard copy mailing list:
Remove ( ) Add ( )
Name:
Address:
City:
State: ZIP