Department of Computer and Information Science

Permanent URI for this community

https://hdl.handle.net/1794/122

For information about the department, please see the department's web site.

Browse

Now showing 1 - 20 of 27

Open Access
Macros That Work
(University of Oregon, 1991-01) Clinger, William D.; Rees, Jonathan
This paper describes a modified form of Kohlbecker's algorithm for reliably hygienic (capture-free) macro expansion in block-structured languages, where macros are source-tos-ource transformations specified using a high-level pattern language. Unlike previous algorithms, the modified algorithm runs in linear instead of quadratic time, copies few constants, does not assume that syntactic keywords ( e.g. if) are reserved words, and allows local (scoped) macros to refer to lexical variables in a referentially transparent manner. Syntactic closures have been advanced as an alternative to hygienic macro expansion. The problem with syntactic closures is that they are inherently low-level and therefore difficult to use correctly, especially when syntactic keywords are not reserved. It is impossible to construct a pattern-based, automatically hygienic macro system on top of syntactic closures because the pattern interpreter must be able to determine the syntactic role of an identifier (in order to close it in the correct syntactic environment) before macro expansion has made that role apparent. may be viewed as a book-keeping technique for deferring such decisions until macro expansion is locally complete. Building on that insight, this paper unifies and extends the competing paradigms of hygienic macro expansion and syntactic closures to obtain an algorithm that combines the benefits of both . Several prototypes of a complete macro system for Scheme have been based on the algorithm presented here.
Open Access
How to Read Floating Point Numbers
(University of Oregon, 1990-06-05) Clinger, William D.
Consider the problem of converting decimal scientific notation for a number into the best binary floating point approximation to that number, for some fixed precision. This problem cannot be solved using arithmetic of any fixed precision. Hence the IEEE Standard/or Binary Floating-Point Arithmetic does not require the result of such a conversion to be the best approximation. This paper presents an efficient algorithm that always·finds the best approximation. The algorithm uses a few extra bits of precision to compute an IEEE-conforming approximation while testing an intermediate result to determine whether the approximation could be other than the best. If the approximation might not be the best, then the best approximation is determined by a few simple operations on multiple-precision integers, where the precision is determined by the input When using 64 bits of precision to compute IEEE double precision results, the algorithm avoids higher-precision arithmetic over 99% of the time. The input problem considered by this papet is the inverse of an output problem considered by Steele and White: Given a binary floating point number, print a correctly rounded decimal representation of it using the smallest number of digits that will allow the number to be read without loss of accuracy. The Steele and White algorithm assumes that the input problem is solved; an imperfect solution to the input problem, as allowed by the IEEE standard and ubiquitous in current practice, defeats the purpose of their algorithm.
Open Access
Broadcast Time in Communication Networks
(University of Oregon, 1979-05) Blaha, Kenneth D.
Broadcasting is the information dissemination process whereby a set of messages is transmitted from one member to all other members of a communication network . We model a communication network by a graph and place certain restrictions upon the broadcasting process. Upper and lower bounds on the time to broadcast m messages throughout a network of n members are determined. Other time-related issues are addressed, including the estimation of time-optimal segmentation o f messages which are to be broadcast .
Open Access
Broadcasting in Trees with Multiple Originators
(University of Oregon, 1980) Farley, Arthur M.; Proskurowski, Andrzej
Broadcasting is the information dissemination process in a communication network whereby all sites of the network become informed of a given message by calls made over lines of the network. We present an algorithm which, given a tree network and a time, determines a smallest set of subtrees covering sites of the network such that broadcast can be completed within the given time in each subtree. Information developed by the algorithm is sufficient to determine a satisfactory originator and calling scheme within each subtree.
Open Access
Negotiation Behavior During Multiple Agent Specification: A Need for Automated Conflict Resolution
(University of Oregon, 1989-09-06) Robinson, Willam N.
Negotiation is part of specification. During specification acquisition, users negotiate amongst themselves and with analysts. During specification design, designers negotiate amongst themselves and with a project leader. Throughout the specification of a system, people communicate needs and constraints in ways which benefit the project or themselves. The study of such behavior has been valuable to disciplines -such as contract negotiation and office management. However, software engineering has yet to address negotiation behavior. Here we show how negotiation applies to specification. We present automated means to promote integrative behavior during specification. We conclude that formal models of users' desires and resolution methods are necessary for integrative reasoning.
Open Access
Mapping Divide-and-Conquer Algorithms to Parallel Architectures
(University of Oregon, 1990-01-19) Lo, V.; Rajopadhye, S. V.; Gupta, S.; Keldsen, D.; Mohamed, M.; Telle, Jan
In this paper, we identify the binomial tree as an ideal computation structure for parallel divide-and-conquer algorithms. We show its superiority to the classic full binary tree structure with respect to speedup and efficiency. We also present elegant and efficient algorithms for mapping the binomial tree to two interconnection networks commonly used in multicomputers, namely the hypercube and the two-dimensional mesh. Our mappings are optimal with respect to both average dilation and link contention. We discuss the practical implications of these results for message-passing architectures using store-and-forward routing vs. those using wormhole routing.
Open Access
Architected Failure Handling for AND-Parallel Logic Programs
(University of Oregon, 1989-03-24) Meyer, David M.; Conery, John S.
In this paper, we present an architected approach to failure handling for independent AND parallel logic programs. That is, the architecture presented here represents its failure handling algorithm as a sequence of simple abstract machine instructions, rather than as a built-in function. Information about data dependencies is used by a compiler to generate special purpose fail routines on a clause-by-clause basis. We also present two simple optimizations that further specialize the handling of failures for each clause.
Open Access
A Determinacy Testing Algorithm for Nondeterminate Flat Concurrent Logic Programming Languages
(University of Oregon, 1990-11) Tick, E.; Korsloot, M.
This paper describes an algorithm for the code generation of determinacy testing for nondeterminate flat concurrent logic programming languages. Languages such as Andorra and Pandora require that procedure invocations suspend if there is more than one candidate clause potentially satisfying the goal. The algorithm described has been developed specifically for a variant of flat Pandora based on FGHC, although the concepts are general. We have extended Kliger and Shapiro's decision-graph construction algorithm to compile "don't know" procedures which must suspend for nondeterminate goal invocation. The determinacy test is compiled into a decision graph quite different from those of committed-choice procedures, but we argue that in most cases, the same low space complexity is retained.
Open Access
Reliability of Partial k-tree Networks
(University of Oregon, 1990-06-08) Mata-Montero, Erick
Recent developments in graph theory have shown the importance of the class of partial k- trees. This large class of graphs admits several algorithm design methodologies that render efficient solutions for a large number of problems inherently difficult for general graphs. In this thesis we develop such algorithms to solve a variety of reliability problems on partial k-tree networks with node and edge failures. We also investigate the problem of designing uniformly optimal 2-trees with respect to the 2-terminal reliability measure. We model a. communication network as a graph in which nodes represent communication sites and edges represent bidirectional communication lines. Each component (node or edge) has an associated probability of operation. Components of the network are in either operational or failed state and their failures are statistically independent. Under this model, the reliability of a network G is defined as the probability that a given connectivity condition holds. The l-terminal reliability of G, Rel1 ( G), is the probability that any two of a given set of I nodes of G can communicate. Robustness of a network to withstand failures can be expressed through network resilience, Res( G), which is the expected number of distinct pairs of nodes that can communicate. Computing these and other similarly defined measures is #P-hard for general networks. We use a dynamic programming paradigm to design linear time algorithms that compute Rel1( G), Res( G), and some other reliability and resilience measures of a partial k-tree network given with an embedding in a k-tree (for a fixed k). Reliability problems on directed networks are also inherently difficult. We present efficient algorithms for directed versions of typical reliability and resilience problems restricted to partial k-tree networks without node failures. Then we reduce to those reliability problems allowing both node and edge failures. Finally, we study 2-terminal reliability aspects of 2-trees. We characterize uniformly optimal 2-trees, 2-paths, and 2-caterpillars with respect to Rel2 and identify local graph operations that improve the 2-terminal reliability of 2-tree networks.
Open Access
Resilience of Partial k-tree Networks
(University of Oregon, 1989-10-20) Mata-Montero, Erick
The resilience of a network is the expected number of pairs of nodes that can communicate. Computing the resilience of a network has been shown to be a #P-complete problem for planar networks and to take O(n)^2 time for n-node partial 2-tree networks. We present an O(n) time algorithm to compute the resilience of partial 2-tree networks on n-nodes, and, for a fixed k, an O(n)^2 algorithm to compute the resilience of n-node partial k-tree networks given with an embedding in a k-tree.
Open Access
Resilience of Partial k-tree Networks with Edge and Node Failures
(University of Oregon, 1989-10-20) Mata-Montero, Erick
The resilience of a network is the expected number of pairs of nodes that can communicate. Computing the resilience of a network is a #P-complete problem even for planar networks with fail-safe nodes. We generalize an O(n)^2 time algorithm to compute the resilience of n-node k-tree networks with fail-safe nodes to obtain an O(n) time algorithm that computes the resilience of n-node partial k-tree networks with edge and node failures (given a fixed k and an embedding of the partial k-tree in a k-tree).
Open Access
Little Big LISP
(University of Oregon, 1981-05) Marti, Jed B.
This manual describes the Little Big LISP system for the Z80 microcomputer. The manual describes data structures, defined functions, operating procedures, a compiler, an RLISP parser, and support packages.
Open Access
OREGAMI: Software Tools for Mapping Parallel Computations to Parallel Architectures
(University of Oregon, 1990-01-19) Lo, Virginia M.; Rajopadhye, Sanjay; Gupta, Samik; Keldsen, David; Mohamed, Moataz A.; Telle, Jan
The mapping problem in message-passing parallel processors involves the assignment of tasks in a parallel computation to processors and the routing of inter-task messages along the links of the interconnection network. We have developed a unified set of software tools called OREGAMI for automatic and guided mapping of parallel computations to parallel architectures in order to achieve portability and maximal performance from parallel systems. Our tools include a description language which enables the programmer of parallel algorithms to specify information about the static and dynamic communication behavior of the computation to be mapped. This information is used by the mapping algorithms to assign tasks to processors and to route communication in the network topology. Two key features of our system are (a) the ability to take advantage of the regularity present in both the computation structure and the interconnection network and (b) the desire to balance the user's knowledge and intuition with the computational power of efficient combinatorial algorithms.
Open Access
RAGA: Musical Gantt Charts for Scheduling in Distributed Real Time Systems
(University of Oregon, 1991-01) Lo, Virginia M.; Pall, Gurdeep Singh
We propose a simple extension to Gantt charts, called RAGA scores, for use in distributed real time scheduling. RAGA scores use a small set of symbols borrowed from musical notation to enrich the expressive power of the Gantt chart. These symbols enable the timing constraints of real time tasks to be displayed along with the schedule itself. Because of the criticality of timing constraints in real time systems , it is important to be able to visualize these constraints and the schedule simultaneously. The RAGA score is encapsulated as an abstract data type (ADT) that can be used as a tool in the design and visualization of static and dynamic scheduling algorithms, in the display of real time schedules for performance evaluation through simulation, and for historical records of actual schedules for performance evaluation through 'execution traces. '
Open Access
Distributed Shared Memory: A Survey of Issues and Algorithms
(University of Oregon, 1991-01-07) Lo, Virginia M.; Nitzberg, Bill
A distributed shared memory (DSM) is an implementation of the shared memory abstraction on a multicomputer architecture which has no physically shared memory. Shared memory is important (as a programming model) not only because of the vast number of existing applications which use it, but also because it is a more appropriate paradigm for certain algorithms. The DSM concept was demonstrated to be viable by Li, in IVY. Recently, there has been a surge of new projects which implement DSM in a variety of software and hardware environments. This paper gives an integrated overview of distributed shared memory. We discuss theoretical lower bounds on the performance of DSM systems, design choices such as structure and granularity, access, coherence semantics, scalability, and heterogeneity, and open problems in DSM. In addition, we describe algorithms used to implement and improve efficiency: reducing thrashing, eliminating false sharing, matching the coherence protocol to the type of sharing, and relaxing the semantics of the memory coherence provided. A spectrum of current DSM systems are used as illustrative examples.
Open Access
Algorithms For Static Task Assignment And Symmetric Contraction In Distributed Computing Systems
(University of Oregon, 1988-05-05) Lo, Virginia M.
In this paper, we look at the mapping problem, which was posed within the domain of parallel processing, and we redefine that problem for use in distributed computing systems whose underlying communication medium is a broadcast medium such as ethernet. We describe an efficient algorithm which can be utilized to find optimal assignments of tasks to processors for a wide variety of distributed algorithms when symmetric contraction of the algorithm is necessary. 'Ne also describe a heuristic algorithm for use in finding suboptimal assignments of tasks to processors for arbitrary distributed computations. Both algorithms model the mapping problem as the Graph Partitioning Problem. Our algorithms utilize an efficient algorithm for finding maximum weight matchings to find an assignment of tasks to processors which minimizes the total interprocessor communication cost while meeting a constraint on the number of tasks assigned to each processor.
Open Access
Fast Parallel Algorithms for the Subgraph Homeomorphism & the Subgraph Isomorphism Problems for Classes of Planar Graphs
(University of Oregon, 1988-04-06) Lingas, Andrzej; Proskurowski, Andrzej
We consider the problems of subgraph homeomorphism with fixed pattern graph, recognition, and subgraph isomorphism for some classes of planar graphs. Following the results of Robertson and Seymour on forbidden minor characterization, we show that the problems of fixed subgraph homeomorphism and recognition for any family of planar graphs closed under minor taking are in NC (i.e., they can be solved by an algorithm running in poly-log time using polynomial number of processors). We also show that the related subgraph isomorphism problem for biconnected outerplanar ·graphs is in NC. This is the first example of a restriction of subgraph isomorphism to a non-trivial graph family admitting an NC algorithm
Open Access
Design Issues in a Minimal Language to Support Lisp-based, Object-based, and Rule-based Programming
(University of Oregon, 1988-12-30) Fickas, Stephen; Doerry, Eckehard; Meyer, David; Miller, Peter
In this paper we argue for a minimalist view of language design for Expert System environments. In support of our arguments we present MIN, a minimal language which extends the less-is-better philosophy of Scheme to include both object-based and rule-based components. We discuss the strengths and weaknesses of MIN as an embodiment of the minimalist philosophy, and point to other work supporting this view of language design.
Open Access
A Proposed Perspective Shift: Viewing Specification Design as a Planning Problem
(University of Oregon, 1988-11-17) Fickas, Stephen; Anderson, John
We argue that in certain problem domains, AI planning can be viewed as a foundation for generation, critiquing, and elaboration of a specification. Two specification design projects in our group are used as a focus of discussion .
Open Access
The Design of Template Immune Networks: Path Immunity
(University of Oregon, 1989-03-24) Farley, Arthur M.; Proskurowski, Andrzej
A network is specified by a topology definition and a protocol definition. A network's topology, represented as a graph, defines its interconnection structure, while the protocol defines its operational behavior. A template is a connected graph. A topology G is immune to a set of templates T if G remains connected under removal of any imbedding of a single element of T. A network is template immune to a set of templates T if its topology is immune to T and its protocol guarantees that all operative sites can communicate in the presence of possible failures. A network is isolated template immune to a set of templates T if it is immune to multiple imbeddings of elements of T, where each imbedded template does not involve vertices that are neighbors of another imbedded template. We discuss networks that are isolated template immune to simple path templates of length k.