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
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
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
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
Context, User Models and Interface Design
(University of Oregon, 1988-07-12) Douglas, Sarah A.
Most of the existing analytical descriptions of users characterize their performance as a function of the cognitive representation of the command sequences of the computer-based task (e.g. Anderson, Farrell, & Sauers, 1984; Card, Moran & Newell, 1983; Polson & Kieras, 1985; Norman, 1986). This is represented as goal-oriented schemata: procedures, plans, or production rules. Thus, the interface designer need only lay out the command sequences adequate to achieve a set of core tasks to make predictions about user behavior. These models are by and large restricted to descriptions of error-free, skilled (expert) performance or error-free learner subsets of expert knowledge. Attempts to extend these analytical models to accommodate learner error soon find themselves coping with the problems of prior knowledge (c.f. Douglas & Moran, 1983; Riley, 1986). That is, elements of performance that are independent of the computer task representation. Additionally, the existing models make no attempt to represent the ongoing interactive nature of human behavior at the interface. This problem of taking into account aspects of human performance at the interface which are independent of the task representation can be called the context problem. In the remainder of this paper I will attempt to delineate the nature of this problem by defining the notion of context, giving examples of context accommodation in interface design, and discussing the practical and theoretical problems that context creates for user models and interface design.
Open Access
Cooperative Policy Control for Peer-to-Peer Data Distribution
(2010-03-10T22:33:16Z) Anderson, Eric; Li, Jun
Many network applications (such as swarming downloads, peer-to-peer video streaming and file sharing) are made possible by using large groups of peers to distribute and process data. Securing data in such a system requires not just data originators, but also those “distributors,” to enforce access control, verify integrity, or make other content-specific security decisions for the replicated or adapted data. In this paper, we introduce the concepts of cooperative policy enforcement and request type checking, and propose an implementation framework Q which uses these approaches to secure data in peer-to-peer systems. The Q framework associates every data object with relocatable policy descriptors which distributors can use to determine whether a request for that object should be granted and whether a data transfer meets a request. With minimal changes to the application or the framework, Q can define and enforce arbitrarily sophisticated policies across a wide range of applications. Policies can be written to work across applications, or to include application-specific criteria and behavior. We will also discuss integrating Q with several peer-to-peer applications, including Gnutella, distributed hash tables such as CAN and Chord, peer-to-peer video streaming, HTTP swarming and application-level routing.
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
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.
Open Access
Detecting and Repairing Tutoring Failures
(University of Oregon, 1988-06-21) Douglas, Sarah A.
During the course of studying a number of protocols of human tutors working with human students, I became aware of a complex process of interaction failure and repair. Although much ITS research has been devoted to the understanding and modeling of the detection and repair of student performance failure and misconception in learning curriculum concepts, there is little understanding of an equivalent self-detection and repair issue with tutor performance failure and misconception about what the student is taught. Indeed, there seems to have been a failure to examine the heart of intelligent tutoring systems, what Wenger ( 1987) terms knowledge communication. Communication is an inherent dyadic relation whose primary performance feature is interaction. In particular, interaction between humans, as all human performance, appears filled with both slips and bugs. Humans are highly tuned to the detection and repair of these problems. In the remainder of this paper, I present examples of some of the types of tutor interaction failure that I discovered in these protocols, discuss the detection and repair strategies used, and, finally, discuss the implications of these findings for ITS. My conclusion about tutoring failures is that some types can possibly be reduced by use of an intelligent tutoring system, but that others, called model failures, are an inherent part of the teaching of complex domains. Knowledge and the communication of knowledge are inextricably intertwined. Since we cannot create error-free ITS, we should study in more detail the mechanisms of failure detection and repair that are inherent in human interaction. I believe that achieving this goal will require a much finer grain of analysis of the process of student response during both problem .presentation and remediation and will place a greater emphasis on the detailed design of the interface of ITS.
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
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
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
GLOWS: A high-fidelity worm simulator
(2006) Ehrenkranz, Toby; Knickerbocker, Paul, 1980-; Li, Jun; Stafford, Shad
This work presents our GLOWS (Gateway Level Oregon Worm Simulator) simulator, designed to produce realistic worm traffic over a broad range of scenarios. GLOWS simulates the spread of a worm across the Internet and its propagation into a single domain with the goal of capturing the worm traffic that crosses the gateway point separating the monitored domain from the Internet.
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
The Hybrid Solution for Concurrent Operations on B-Trees
(University of Oregon, 1980-03) Ellis, Carla Schlatter
B-trees are useful for supporting large ordered indexes in database systems. Several solutions have recently been proposed to deal with the problem of allowing concurrent operations in data structures related to B-trees. In this paper, the strengths and weaknesses of two of these solutions are described. A combined approach is presented that can be tuned to satisfy specific performance requirements. Informal arguments for the correctness of this new solution are given.
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
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
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
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
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.