bluuebunny/crossref_metadata_2025_split huggingface dataset:
Implications of hierarchical N-body methods for multiprocessor architectures
Authors: Singh Jaswinder Pal , Hennessy John L. , Gupta Anoop 
Published: July 2002

To design effective large-scale multiprocessors, designers need to understand the characteristics of the applications that will use the machines. Application characteristics of particular interest include the amount of communication relative to computation, the structure of the communication, and the local cache and memory requirements, as well as how these characteristics scale with larger problems and machines. One important class of applications is based on hierarchical N-body methods, which are used to solve a wide range of scientific and engineering problems efficiently. Important characteristics of these methods include the nonuniform and dynamically changing nature of the domains to which they are applied, and their use of long-range, irregular communication. This article examines the key architectural implications of representative applications that use the two dominant hierarchical N-body methods: the Barnes-Hut Method and the Fast Multipole Method.
We first show that exploiting temporal locality on accesses to communicated data is critical to obtaining good performance on these applications and then argue that coherent caches on shared-address-space machines exploit this locality both automatically and very effectively. Next, we examine the implications of scaling the applications to run on larger machines. We use scaling methods that reflect the concerns of the application scientist and find that this leads to different conclusions about how communication traffic and local cache and memory usage scale than scaling based only on data set size. In particular, we show that under the most realistic form of scaling, both the communication-to-computation ratio as well as the working-set size (and hence the ideal cache size per processor) grow slowly as larger problems are run on larger machines. Finally, we examine the effects of using the two dominant abstractions for interprocessor communication: a shared address space and explicit message passing between private address spaces. We show that the lack of an efficiently supported shared address space will substantially increase the programming complexity and performance overheads for these applications.
Supporting concurrency, communication, and synchronization in human-computer interaction—the Sassafras UIMS
Authors: Hill Ralph D. 
Published: July 2002

Sassafras is a prototype User Interface Management System (UIMS) specifically designed to support a wide range of user interface styles. In particular, it supports the implementation of user interfaces where the user is free to manipulate multiple input devices and perform several (possibly related) tasks concurrently. These interfaces can be compactly represented and efficiently implemented without violating any of the rules of well-structured programming. Sassafras also supports elaborate run-time communication and synchronization among the modules that make up the user interface. This is needed to implement user interfaces that have context-sensitive defaults, and it simplifies recovery from semantic errors.
Sassafras is based on a new language for specifying the syntax of human-computer dialogues known as Event-Response Language (ERL) and a new run-time structure and communication mechanism for UIMSs known as the Local Event Broadcast Method (LEBM). Both ERL and LEBM are described in detail, and implementation techniques are presented. The effectiveness of Sassafras is demonstrated by describing two interfaces that have been implemented with Sassafras.
Learning to reason
Authors: Khardon Roni , Roth Dan 
Published: July 2002

We introduce a new framework for the study of reasoning. The Learning (in order) to Reason approach developed here views learning as an integral part of the inference process, and suggests that learning and reasoning should be studied together.

The Learning to Reason framework combines the interfaces to the world used by known learning models with the reasoning task and a performance criterion suitable for it. In this framework, the intelligent agent is given access to its favorite learning interface, and is also given a grace period in with it can interact with this interface and construct a representation KB of the world
W
. The reasoning performance is measured only after this period, when the agent is presented with queries α from some query language, relevant to the world, and has to answer whether
W
implies α.

The approach is meant to overcome the main computational difficulties in the traditional treatment of reasoning which stem from its separation from the “world”. Since the agent interacts with the world when construction its knowledge representation it can choose a representation that is useful for the task at hand. Moreover, we can now make explicit the dependence of the reasoning performance on the environment the agent interacts with.
We show how previous results from learning theory and reasoning fit into this framwork and illustrate the usefulness of the Learning to Reason approach by exhibiting new results that are not possible in the traditional setting. First, we give Learning to Reason algorithms for classes of propositional languages for which there are no efficient reasoning algorithms, when represented as a traditional (formula-based) knowledge base. Second, we exhibit a Learning to Reason algorithm for a class of propositional languages that is not know to be learnable in the traditional sense.
Performance estimation of embedded software with instruction cache modeling
Authors: Li Yau-Tsun Steven , Malik Sharad , Wolfe Andrew 
Published: July 2002

Embedded systems generally interact in some way with the outside
world. This may involve measuring sensors and controlling actuators, communicating with other systems, or interacting with users. These functions impose real-time constraints on system design. Verification of these specifications requires computing an upper bound on the worst-case execution time (WCET) of a hardware/software system. Furthermore, it is critical to derive a tight upper bound on WCET in order to make efficient use of system resources.
The problem of bounding WCET is particularly difficult on modern processors. These processors use cache-based memory systems that vary memory access time based on the dynamic memory access pattern of the program. This must be accurately modeled in order to tightly bound WCET. Several analysis methods have been proposed to bound WCET on processors with instruction caches. Existing approaches either search all possible program paths, an intractable problem, or they use highly pessimistic assumptions to limit the search space. In this paper we present a more effective method for modeling instruction cache activity and computing a tight bound on WCET. The method uses an integer linear programming formulation and does not require explicit enumeration of program paths. The method is implemented in the program cinderella and we present some experimental results of this implementation.
Efficient algorithms for inverting evolution
Authors: Farach Martin , Kannan Sampath 
Published: July 2002

Evolution can be mathematically modelled by a stochastic process that operates on the DNA of species. Such models are based on the established theory that the DNA sequences, or genomes, of all extant species have been derived from the genome of the common ancestor of all species by a process of random mutation and natural selection.
A stochastic model of evolution can be used to construct phylogenies, or evolutionary trees, for a set of species. Maximum Likelihood Estimation (MLE) methods seek the evolutionary tree which is most likely to have produced the DNA under consideration. While these methods are intellectually satisfying, they have not been widely accepted because of their computational intractability.
In this paper, we address the intractability of MLE methods as follows: We introduce a metric on stochastic process models of evolution. We show that this metric is meaningful by proving that in order for any algorithm to distinguish between two stochastic models that are close according to this metric, it needs to be given many observations. We complement this result with a simple and efficient algorithm for inverting the stochastic process of evolution, that is, for building a tree from observations on two-state characters. (We will use the same techniques in a subsequent paper to solve the problem for multistate characters, and hence for building a tree from DNA sequence data.) The tree we build is provably close, in our metric, to the tree generating the data and gets closer as more observations become available.

Though there have been many heuristics suggested for the problem of finding good approximations to the most likely tree, our algorithm is the first one with a guaranteed convergence rate, and further, this rate is within a polynomial of the lower-bound rate we establish. Ours is also the first polynomial-time algorithm that is
proven
to converge at all to the correct tree.
Concepts and capabilities of a database computer\
Authors: Banerjee Jayanta , Hsiao David K. , Baum Richard I. 
Published: July 2002

The concepts and capabilities of a database computer (DBC) are given in this paper. The proposed design overcomes many of the traditional problems of database system software and is one of the first to describe a complete data-secure computer capable of handling large databases.
This paper begins by characterizing the major problems facing today's database system designers. These problems are intrinsically related to the nature of conventional hardware and can only be solved by introducing new architectural concepts. Several such concepts are brought to bear in the later sections of this paper. These architectural principles have a major impact upon the design of the system and so they are discussed in some detail. A key aspect of these principles is that they can be implemented with near-term technology. The rest of the paper is devoted to the functional characteristics and the theory of operation of the DBC. The theory of operation is based on a series of abstract models of the components and data structures employed by the DBC. These models are used to illustrate how the DBC performs access operations, manages data structures and security specifications, and enforces security requirements. Short Algol-like algorithms are used to show how these operations are carried out. This part of the paper concludes with a high-level description of the DBC organization. The actual details of the DBC hardware are quite involved and so their presentation is not the subject of this paper.
A sample database is included in the Appendix to illustrate the working of the security and clustering mechanisms of the DBC.
The Multics virtual memory
Authors: Bensoussan A. , Clingen C. T. , Daley R. C. 
Published: July 2002

As experience with use of on-line operating systems has grown, the need to share information among system users has become increasingly apparent. Many contemporary systems permit some degree of sharing. Usually, sharing is accomplished by allowing several users to share data via input and output of information stored in files kept in secondary storage. Through the use of segmentation, however, Multics provides direct hardware addressing by user and system programs of all information, independent of its physical storage location. Information is stored in segments each of which is potentially sharable and carries its own independent attributes of size and access privilege.
Here, the design and implementation considerations of segmentation and sharing in Multics are first discussed under the assumption that all information resides in a large, segmented main memory. Since the size of main memory on contemporary systems is rather limited, it is then shown how the Multics software achieves the effect of a large segmented main memory through the use of the Honeywell 645 segmentation and paging hardware.
A generalization of AVL trees
Authors: Foster Caxton C. 
Published: July 2002

A generalization of AVL trees is proposed in which imbalances up to Δ are permitted, where Δ is a small integer. An experiment is performed to compare these trees with standard AVL trees and with balanced trees on the basis of mean retrieval time, of amount of restructuring expected, and on the worst case of retrieval time. It is shown that, by permitting imbalances of up to five units, the retrieval time is increased a small amount while the amount of restructuring required is decreased by a factor of ten.
A few theoretical results are derived, including the correction of an earlier paper, and are duly compared with the experimental data. Reasonably good correspondence is found.
Using synthetic images to register real images with surface models
Authors: Horn Berthold K. P. , Bachman Brett L. 
Published: July 2002

A number of image analysis tasks can benefit from registration of the image with a model of the surface being imaged. Automatic navigation using visible light or radar images requires exact alignment of such images with digital terrain models. In addition, automatic classification of terrain, using satellite imagery, requires such alignment to deal correctly with the effects of varying sun angle and surface slope. Even inspection techniques for certain industrial parts may be improved by this means.
We achieve the required alignment by matching the real image with a synthetic image obtained from a surface model and known positions of the light sources. The synthetic image intensity is calculated using the reflectance map, a convenient way of describing surface reflection as a function of surface gradient. We illustrate the technique using LANDSAT images and digital terrain models.
Canonical structure in attribute based file organization
Authors: Wong Eugene , Chiang T. C. 
Published: July 2002

A new file structure for attribute based retrieval is proposed in this paper. It allows queries involving arbitrary Boolean functions of the attribute-value pairs to be processed without taking intersections of lists. The structure is highly dependent on the way in which the file is to be used and is uniquely determined by the specification of the allowed queries. Thus, for example, the structure for retrieval on the basis of ranges of values on a given attribute would be very different from one where only retrieval on the basis of a single value is permitted.
The file organization being proposed is based on the atoms of a Boolean algebra generated by the queries. The desirable properties claimed for this structure are proved, and file maintenance questions are discussed.
Scientific Applications: BRAD
Authors: Ophir D. , Rankowitz S. , Shepherd B. J. , Spinrad R. J. 
Published: July 2002

A multiconsole computer display system has been designed that provides very rich displays at low unit cost. Each BRAD (Brookhaven RAster Display) console can plot tens of thousands of points, or up to 4000 characters at 30 frames per second. After an initial display system investment of $50,000, each display, with teletype, cost less than $3,000.
The technique employed is that of programmatically generating a binary image of the desired display in a computer. The image is written on a rotating drum memory. Independent read heads continuously display the picture, which is generated by swept horizontal lines. A standard TV monitor serves as the display device.
The technique has two drawbacks. A computer must compute any image to be displayed. Also, the “pointing” interaction is more difficult. This is because the pointing function gives only the coordinates of the point on the screen. The inverse of the map generation process is required to calculate the coordinates at the input space.
GEORGE 3—A general purpose time sharing and operating system
Authors: Oestreicher M. D. , Bailey M. J. , Strauss J. I. 
Published: July 2002

An Operating System is described which will run on a wide variety of configurations of the I.C.T. 1900, and can handle a large number of online console users while at the same time running several offline (background) jobs. The system is not oriented towards either mode and can be either a batch processing system (such as the ATLAS Supervisor, IBSYS, or GECOS), or a multiaccess system (resembling, to the user, CTSS or MULTICS), or both simultaneously, depending on the installation, which can adjust the Schedulers.
Both online users and offline jobs use a common Command Language. The system includes a Multilevel device-independent File Store.
Some effects of the 6600 computer on language structures
Authors: Allard R. W. , Wolf K. A. , Zemlin R. A. 
Published: July 2002

The problem of compiling efficient 6600 codes prompted the development of an intermediate language reflecting the structure of the machine, that is more easily manipulated in improving object program efficiency. The subject of this paper is the intermediate language and methods of manipulating it.
Compilations of a series of arithmetic statements are discussed. It is assumed that all functions and exponentials have been removed from these statements, and replaced by simple variables. For purposes of simplicity the treatment of subscripts is ignored.
A simplified 6600 structure is presented to illustrate the compiling method. Several assumptions are made for purposes of simplification, although there are cases in which the assumptions are violated in the actual machine.
A general approach to dynamic packet routing with bounded buffers
Authors: Broder Andrei Z. , Frieze Alan M. , Upfal Eli 
Published: July 2002

We prove a sufficient condition for the stability of dynamic packet routing algorithms. Our approach reduces the problem of steady state analysis to the easier and better understood question of static routing. We show that certain high probability and worst case bounds on the quasi-static (finite past) performance of a routing algorithm imply bounds on the performance of the dynamic version of that algorithm. Our technique is particularly useful in analyzing routing on networks with bounded buffers where complicated dependices make standard queuing techniques inapplicable.
We present several applications of our approach. In all cases we start from a known static algorithm, and modify it to fit our framework. In particular we give the first dynamic algorithms for routing on a butterfly or two-dimensional mesh with bounded buffers. Both the injection rate for which the algorithm is stable, and the expected time a packet spends in the system are optimal up to constant factors. Our approach is also applicable to the recently introduced adversarial input model.
Fixed versus variable order Runge-Kutta
Authors: Shampine L. F. , Baca L. S. 
Published: July 2002

Popular codes for the numerical solution of nonstiff ordinary differential equations (ODEs) are based on a (fixed order) Runge-Kutta method, a variable order Adams method, or an extrapolation method. Extrapolation can be viewed as a variable order Runge-Kutta method. It is plausible that variation of order could lead to a much more efficient Runge-Kutta code, but numerical comparisons have been contradictory.
We reconcile previous comparisons by exposing differences in testing methodology and incompatibilities of the implementations tested. An experimental Runge-Kutta code is compared to a state-of-the-art extrapolation code. With some qualifications, the extrapolation code shows no advantage. Extrapolation does not appear to be a particularly effective way to vary the order of Runge-Kutta methods. Although an acceptable way to solve nonstiff problems, our tests raise the question as to whether there is any point in pursuing it as a separate method.
Partitioned signature files: design issues and performance evaluation
Authors: Lee Dik Lun , Leng Chun-Wu 
Published: July 2002

A signature file acts as a filtering mechanism to reduce the amount of text that needs to be searched for a query. Unfortunately, the signature file itself must be exhaustively searched, resulting in degraded performance for a large file size. We propose to use a deterministic algorithm to divide a signature file into partitions, each of which contains signatures with the same “key.” The signature keys in a partition can be extracted and represented as the partition's key. The search can then be confined to the subset of partitions whose keys match the query key. Our main concern here is to study methods for obtaining the keys and their performance in terms of their ability to reduce the search space.
Owing to the reduction of search space, partitioning a signature file has a direct benefit in a sequential search (single-processor) environment. In a parallel environment, search can be conducted in parallel effectively by allocating one or more partitions to a processor. Partitioning the signature tile with a deterministic method (as opposed to a random partitioning scheme) provides intraquery parallelism as well as interquery parallelism.
In this paper, we outline the criteria for evaluating partitioning schemes. Three algorithms are described and studied. An analytical study of the performance of the algorithms is provided and the results are verified with simulation.
Imaging Cognition II: An Empirical Review of 275 PET and fMRI Studies
Authors: Cabeza Roberto , Nyberg Lars 
Published: July 2002

Abstract
Positron emission tomography (PET) and functional magnetic resonance imaging (fMRI) have been extensively used to explore the functional neuroanatomy of cognitive functions. Here we review 275 PET and fMRI studies of attention (sustained, selective, Stroop, orientation, divided), perception (object, face, space/motion, smell), imagery (object, space/ motion), language (written/spoken word recognition, spoken/ no spoken response), working memory (verbal/numeric, object, spatial, problem solving), semantic memory retrieval (categorization, generation), episodic memory encoding (verbal, object, spatial), episodic memory retrieval (verbal, nonverbal, success, effort, mode, context), priming (perceptual, conceptual), and procedural memory (conditioning, motor, and nonmotor skill learning). To identify consistent activation patterns associated with these cognitive operations, data from 412 contrasts were summarized at the level of cortical Brodmann's areas, insula, thalamus, medial-temporal lobe (including hippocampus), basal ganglia, and cerebellum. For perception and imagery, activation patterns included primary and secondary regions in the dorsal and ventral pathways. For attention and working memory, activations were usually found in prefrontal and parietal regions. For language and semantic memory retrieval, typical regions included left prefrontal and temporal regions. For episodic memory encoding, consistently activated regions included left prefrontal and medial-temporal regions. For episodic memory retrieval, activation patterns included prefrontal, medial-temporal, and posterior midline regions. For priming, deactivations in prefrontal (conceptual) or extrastriate (perceptual) regions were consistently seen. For procedural memory, activations were found in motor as well as in non-motor brain areas. Analysis of regional activations across cognitive domains suggested that several brain regions, including the cerebellum, are engaged by a variety of cognitive challenges. These observations are discussed in relation to functional specialization as well as functional integration.