bluuebunny/crossref_metadata_2025 huggingface dataset:
A boundary integral equation method using auxiliary interior surface approach for acoustic radiation and scattering in two dimensions
Authors: Yang S. A.
Published: October 2002

This paper presents an effective solution method for predicting acoustic radiation and scattering fields in two dimensions. The difficulty of the fictitious characteristic frequency is overcome by incorporating an auxiliary interior surface that satisfies certain boundary condition into the body surface. This process gives rise to a set of uniquely solvable boundary integral equations. Distributing monopoles with unknown strengths over the body and interior surfaces yields the simple source formulation. The modified boundary integral equations are further transformed to ordinary ones that contain nonsingular kernels only. This implementation allows direct application of standard quadrature formulas over the entire integration domain; that is, the collocation points are exactly the positions at which the integration points are located. Selecting the interior surface is an easy task. Moreover, only a few corresponding interior nodal points are sufficient for the computation. Numerical calculations consist of the acoustic radiation and scattering by acoustically hard elliptic and rectangular cylinders. Comparisons with analytical solutions are made. Numerical results demonstrate the efficiency and accuracy of the current solution method.
Detection of static and dynamic changes in interaural correlation
Authors: Boehnke Susan E. , Hall Susan E. , Marquardt Torsten
Published: October 2002

This study examines the relation between a static and a dynamic measure of interaural correlation discrimination: (1) the just noticeable difference (JND) in interaural correlation and (2) the minimum detectable duration of a fixed interaural correlation change embedded within a single noise-burst of a given reference correlation. For the first task, JNDs were obtained from reference interaural correlations of +1, −1, and from 0 interaural correlation in either the positive or negative direction. For the dynamic task, duration thresholds were obtained for a brief target noise of +1, −1, and 0 interaural correlation embedded in reference marker noise of +1, −1, and 0 interaural correlation. Performance with a reference interaural correlation of +1 was significantly better than with a reference correlation of −1. Similarly, when the reference noise was interaurally uncorrelated, discrimination was significantly better for a target correlation change towards +1 than towards −1. Thus, for both static and dynamic tasks, interaural correlation discrimination in the positive range was significantly better than in the negative range. Using the two measures, the length of a binaural temporal window was estimated. Its equivalent rectangular duration (ERD) was approximately 86 ms and independent of the interaural correlation configuration.
English-learning infants use juncture cues to segment speech
Authors: Johnson Elizabeth K.
Published: October 2002

Seven-month-olds perceive recurring sequences of strong–weak (SW) syllables as words, presumably due to their heavy reliance on the metrical segmentation strategy for English. For example, 7-month-olds will segment ‘‘taris’’ from a passage containing repeated tokens of ‘‘guitar is.’’ However, by 10 months, infants no longer make this mistake [Jusczyk et al., Cognit. Psychol. 39, 630–645 (1999)]. There are many possible explanations for this result. Some have argued that 10-month-olds are sensitive to the subtle juncture cues suggesting a word boundary between syllables such as ‘‘tar’’ and ‘‘is.’’ However, others have suggested that 10-month-olds have adopted a lexical segmentation strategy. In other words, infants know common function and auxiliaries such as ‘‘is.’’ Therefore, they know that ‘‘taris’’ cannot be a word. The head-turn preference procedure was used to investigate whether English-learning infants would segment ‘‘toga’’ from ‘‘toe galore’’ just as readily as they would segment ‘‘toga’’ from ‘‘toga lore.’’ Seven-month-olds segmented ‘‘toga’’ equally well in both cases, whereas 12-month-olds failed to segment ‘‘toga’’ from ‘‘toe galore.’’ These results suggest that knowledge of frequently occurring function and auxiliaries cannot explain Jusczyk et al.’s results. Future work will investigate the information infants might use to distinguish ‘‘toe galore’’ from ‘‘toga lore.’’
Informed choice to undergo prenatal screening: a comparison of two hospitals conducting testing either as part of a routine visit or requiring a separate visit
Authors: Dormandy E. , Hooper R. , Michie S. , Marteau T.M.
Published: October 2002

BACKGROUND: It is not known which of two common methods of conducting prenatal screening best facilitate women making informed choices. OBJECTIVE: To describe rates of informed choice in two hospitals: one where screening for Down’s syndrome was conducted at a routine visit; the other where screening was conducted as part of a separate visit. DESIGN: Prospective descriptive study. SETTING: Two hospitals in England. PARTICIPANTS: 1499 pregnant women offered screening for Down’s syndrome. Outcome measure: A multidimensional measure of informed choice derived from measures of (a) consistency between attitudes towards undergoing the test and uptake and (b) knowledge about the screening test. RESULTS: The proportion of women making an informed choice to accept the test was higher at the routine visit hospital than at the separate visit hospital (41% v 21%, 95% confidence interval (95% CI) of the difference 16% to 25%). The proportions of women making an informed choice to decline the test were similar at the two hospitals (23% at both, 95% CI of the difference -5% to 4%). These results reflect the finding that women with negative attitudes were equally likely to decline the test at each of the two hospitals, whereas women with positive attitudes were more likely to accept the test at the routine visit hospital than at the separate visit hospital. This finding held after adjusting for parity, socioeconomic status, age, and ethnicity. At both hospitals, women with good knowledge were slightly more likely to undergo the test than were women with poor knowledge. This difference disappeared after a similar adjustment. CONCLUSION: Screening conducted as part of a routine visit may be associated with higher levels of informed choice than screening conducted at a separate visit. This finding constitutes a hypothesis for experimental investigation.
Early outcome of mammography screening in Copenhagen 1991–99
Authors: Vejborg I. , Olsen A.H. , Jensen M-B. , Rank F. , Tange U.B. , Lynge E.
Published: October 2002

OBJECTIVES: To evaluate the early outcome of an organised mammography screening programme in an area with little opportunistic screening. SETTING: The municipality of Copenhagen, Denmark, during four invitation rounds 1991–99. METHODS: The following outcome measures were used: rates of participation, recall, false positive, and cancer detection. Benign biopsy, distribution of tumour size, lymph node status, and malignancy grade. RESULTS: A total of 106 933 screens were undertaken, and 824 invasive breast carcinomas or CIS were detected. The detection rate was 11.9 per 1000 participants in the first invitation round, and it continued to be high in subsequent rounds. The percentage of CIS cases was 11%. Coverage declined from 71% in the first round to 62% in the fourth, although 91% of those participating in the previous three rounds attended. The programme operated with a high recall rate. The false positive rate was also high, being 5.6% at first screen, and 1.8% later on. However, 90% of false positives were sorted out already at assessment. The percentage of screen detected invasive breast cancers with a tumour diameter ≤10 mm was 39% compared with 16% of all invasive breast cancers in these age groups in Copenhagen before screening. CONCLUSION: Copenhagen is an area with a high incidence of breast cancer and with relatively little opportunistic screening. The start of a screening programme with a high recall rate in this area resulted in a detection rate above 1%. The Copenhagen programme met or exceeded most of the interim measures recommended in the European Guidelines.
Analysis of Or-parallel execution models
Authors: Gupta Gopal , Jayaraman Bharat
Published: October 2002

We discuss fundamental limitations of or-parallel execution models of nondeterministic programming languages. Or-parallelism corresponds to the execution of different nondeterministic computational paths in parallel. A natural way to represent the state of (parallel) execution of a nondeterministic program is by means of an or-parallel tree. We identify three important criteria that underlie the design of or-parallel implementations based on the or-parallel tree: constant-time access to variables, constant-time task creation, and constant-time task switching, where the term
constant-time
means that the time for these operations is independent of the number of nodes in the or-parallel tree, as well as the size of each node. We prove that all three criteria cannot be simultaneously satisfied by any or-parallel execution model based on a finite number of processors but unbounded memory. We discuss in detail the application of our result to the class of logic programming languages and show how our result can serve as a useful way to categorize the various or-parallel methods proposed in this field. We also discuss the suitability of different or-parallel implemenation strategies for different parallel architectures.
A formal definition of priority in CSP
Authors: Fidge C. J.
Published: October 2002

The process models of Ada and occam are formally based on the CSP process algebra. However, for fine-tuning real-time performance, they include “prioritized” constructs that have no counterparts in CSP. These constructs therefore lack any formal definition, a situation that leaves room for misunderstandings. We extend CSP with a formal definition of the notion of priority. The definition is then used to assess the transputer implementation of priority in occam and the definition of priority in Ada.
Avoidance and suppression of compensation code in a trace scheduling compiler
Authors: Freudenberger Stefan M. , Gross Thomas R. , Lowney P. Geoffrey
Published: October 2002

Trace scheduling is an optimization technique that selects a sequence of basic blocks as a trace and schedules the operations from the trace together. If an operation is moved across basic block boundaries, one or more compensation copies may be required in the off-trace code. This article discusses the generation of compensation code in a trace scheduling compiler and presents techniques for limiting the amount of compensation code: avoidance (restricting code motion so that no compensation code is required) and suppression (analyzing the global flow of the program to detect when a copy is redundant). We evaluate the effectiveness of these techniques based on measurements for the SPEC89 suite and the Livermore Fortran Kernels, using our implementation of trace scheduling for a Multiflow Trace 7/300. The article compares different compiler models contrasting the performance of trace scheduling with the performance obtained from typical RISC compilation techniques.

There are two key results of this study. First, the amount of compensation code generated is not large. For the SPEC89 suite, the average code size increase due to trace scheduling is 6%. Avoidance is more important than suppression, although there are some kernels that benefit significantly from compensation code suppression. Since compensation code is not a major issue, a compiler can be more aggressive in code motion and loop unrolling. Second, compensation code is not critical to obtain the benefits of trace scheduling. Our implementation of trace scheduling improves the SPEC mark rating by 30% over basic block scheduling, but restricting trace scheduling so that no compensation code is required improves the rating by 25%. This indicates that most basic block scheduling techniques can be extended to trace scheduling without requiring any complicated compensation code bookkeeping.
Extracting task-level parallelism
Authors: Girkar Milind , Polychronopoulos Constantine D.
Published: October 2002

Automatic detection of
task-level parallelism
(also referred to as functional, DAG, unstructured, or thread parallelism) at various levels of program granularity is becoming increasingly important for parallelizing and back-end compilers. Parallelizing compilers detect iteration-level or coarser granularity parallelism which is suitable for parallel computers; detection of parallelism at the statement-or operation-level is essential for most modern microprocessors, including superscalar and VLIW architectures. In this article we study the problem of detecting, expressing, and optimizing task-level parallelism, where “task” refers to a program statement of arbitrary granularity. Optimizing the amount of functional parallelism (by allowing synchronization between arbitrary nodes) in sequential programs requires the notion of
precedence
in terms of paths in graphs which incorporate control and data dependences. Precedences have been defined before in a different context; however, the definition was dependent on the ideas of parallel execution and time. We show that the problem of determining precedences statically is NP-complete. Determining precedence relationships is useful in finding the essential data dependences. We show that there exists a unique minimum set of essential data dependences; finding this minimum set is NP-hard and NP-easy. We also propose a heuristic algorithm for finding the set of essential data dependences. Static analysis of a program in the Perfect Benchmarks was done, and we present some experimental results.
Backtracking without trailing in CLP (ℜ
Lin
)
Authors: Van Hentenryck Pascal , Ramachandran Viswanath
Published: October 2002

Existing CLP languages support backtracking by generalizing traditional Prolog implementations: modifications to the constraint system are trailed and restored on backtracking. Although simple and efficient, trailing may be very demanding in memory space, since the constraint system may potentially be saved at each choice point.

This article proposes a new implementation scheme for backtracking in CLP languages over linear (rational or real) arithmetic. The new scheme, called
semantic backtracking
, does not use trailing but rather exploits the semantics of the constraints to undo the effect of newly added constraints. Semantic backtracking reduces the space complexity compared to implementations based on trailing by making it essentially independent of the number of choice points. In addition, semantic backtracking introduces negligible space and time overhead on deterministic programs. The price for this improvement is an increase in backtracking time, although constraint-solving time may actually decrease. The scheme has been implemented as part of a complete CLP system CLP (ℜ
Lin
) and compared analytically and experimentally with optimized trailing implementations. Experimental results on small and real-life problems indicate that semantic backtracking produces significant reduction in memory space, while keeping the time overhead reasonably small.
On the optimality of change propagation for incremental evaluation of hierarchical attribute grammars
Authors: Carle Alan , Pollock Lori
Published: October 2002

Several new attribute grammar dialects have recently been developed, all with the common goal of allowing large, complex language translators to be specified through a modular composition of smaller attribute grammars. We refer to the class of dialects as
hierarchical attribute grammars
. In this short article, we present a characterization of optimal incremental evaluation that indicates the unsuitability of change propagation as the basis of an optimal incremental evaluator for hierarchical attribute grammars. This result lends strong support to the use of incremental evaluators based on more applicative approaches to attribute evaluation, such as Carle and Pollock's evaluator based on more applicative approaches to attribute evaluation, such as Carle and Pollock's evaluator based on caching of partially attributed subtree, Pugh's evaluator based on function caching of semantic functions, and Swierstra and Vogt's evaluator based on functions, and Swierstra and Vogt's evaluator based on function caching of visit sequences.
Parallelism for free
Authors: Knoop Jens , Steffen Bernhard , Vollmer Jürgen
Published: October 2002

We consider parallel programs with shared memory and interleaving semantics, for which we show how to construct for unidirectional bitvector problems optimal analysis algorithms that are as efficient as their purely sequential counterparts and that can easily be implemented. Whereas the complexity result is rather obvious, our optimality result is a consequence of a new Kam/Ullman-style Coincidence Theorem. Thus using our method, the standard algorithms for sequential programs computing liveness, availability, very busyness, reaching definitions, definition-use chains, or the analyses for performing code motion, assignment motion, partial dead-code elimination or strength reduction, can straightforward be transferred to the parallel setting at almost no cost.
Demand-driven register allocation
Authors: Proebsting Todd A. , Fischer Charles N.
Published: October 2002

A new global register allocation technique,demand-driven register allocation, is described. Demand-driven register allocation quantifies the costs and benefits of allocating variables to registers over live ranges so that high-quality allocations can be made. Local allocation is done first, and then global allocation is done iteratively beginning in the most deeply nested loops. Because local allocation precedes global allocation, demand-driven allocation does not interfere with the use of well-known, high-quality local register allocation and instruction-scheduling techniques.
Precise flow-insensitive may-alias analysis is NP-hard
Authors: Horwitz Susan
Published: October 2002

Determining aliases is one of the foundamental static analysis problems, in part because the precision with which this problem is solved can affect the precision of other analyses such as live variables, available expressions, and constant propagation. Previous work has investigated the complexity of flow-sensitive alias analysis. In this article we show that precise flow-
insensitive
may-alias analysis is NP-hard given arbitrary levels of pointers and arbitrary pointer dereferencing.
A practical soft type system for scheme
Authors: Wright Andrew K. , Cartwright Robert
Published: October 2002

Asoft type systeminfers types for the procedures and data structures of dynamically typed programs. Like conventional static types, soft types express program invariants and thereby provide valuable information for program optimization and debugging. A soft typecheckeruses the types inferred by a soft type system to eliminate run-time checks that are provably unnecessary; any remaining run-time checks are flagged as potential program errors.Soft Schemeis a practical soft type checker for R4RS Scheme. Its underlying type system generalizes conventional Hindley-Milner type inference by incorporating recursive types and a limited form of union type. Soft Scheme accommodates all of R4RS Scheme including uncurried procedures of fixed and variable arity, assignment, and continuations.
Verifying parameterized networks
Authors: Clarke E. M. , Grumberg O. , Jha S.
Published: October 2002

This article describes a technique based on network grammars and abstraction to verify families of state-transition systems. The family of state-transition systems is represented by a context-free network grammar. Using the structure of the network grammar our technique constructs a process invariant that
simulates
all the state-transition systems in the family. A novel idea introduced in this article is the use of
regular languages
to express state properties. We have implemented our techniques and verified two nontrivial examples.
Constraint-based termination analysis of logic programs
Authors: Decorte Stefaan , De Schreye Danny , Vandecasteele Henk
Published: October 2002

Current norm-based automatic termination analysis techniques for logic programs can be split up into different components: inference of mode or type information, derivation of models, generation of well-founded orders, and verification of the termination conditions themselves. Although providing high-precision results, these techniques suffer from an efficiency point of view, as several of these analyses are often performed through abstract interpretation. We present a new termination analysis which integrates the various components and produces a set of constraints that, when solvable, identifies successful termination proofs. The proposed method is both efficient and precise. The use of constraint sets enables the propagation on information over all different phases while the need for multiple analyses is considerably reduced.
Incremental analysis of constraint logic programs
Authors: Hermenegildo Manuel , Puebla German , Marriott Kim , Stuckey Peter J.
Published: October 2002

Global analyzers traditionally read and analyze the entire program at once, in a nonincremental way. However, there are many situations which are not well suited to this simple model and which instead require reanalysis of certain parts of a program which has already been analyzed. In these cases, it appears inefficient to perform the analysis of the program again from scratch, as needs to be done with current systems. We describe how the fixed-point algorithms used in current generic analysis engines for (constraint) logic programming languages can be extended to support incremental analysis. The possible changes to a program are classified into three types: addition, deletion, and arbitrary change. For each one of these, we provide one or more algorithms for identifying the parts of the analysis that must be recomputed and for performing the actual recomputation. The potential benefits and drawbacks of these algorithms are discussed. Finally, we present some experimental results obtained with an implementation of the algorithms in the PLAI generic abstract interpretation framework. The results show significant benefits when using the proposed incremental analysis algorithms.
Generation of LR parsers by partial evaluation
Authors: Sperber Michael , Thiemann Peter
Published: October 2002

The combination of modern programming languages and partial evaluation yields new approaches to old problems. In particular, the combination of functional programming and partial evaluation can turn a general parser into a parser generator. We use an inherently functional approach to implement general LR(
k
) parsers and specialize them with respect to the input grammars using offline partial evaluation. The functional specification of LR parsing yields a concise implementation of the algorithms themselves. Furthermore, we demonstrate the elegance of the functional approach by incorporating on-the-fly attribute evaluation for S-attributed grammars and two schemes for error recovery, which lend themselves to natural and elegant implementation. The parser require only minor changes to achieve good specialization results. The generated parsers have production quality and match those produced by traditional parser generators in sped and compactness
An Improved Context-Free Recognizer
Authors: Graham Susan L. , Harrison Michael , Ruzzo Walter L.
Published: October 2002

A new algorithm for recognizing and parsing arbitrary context-free languages is presented, and several new results are given on the computational complexity of these problems. The new algorithm is of both practical and theoretical interest. It is conceptually simple and allows a variety of efficient implementations, which are worked out in detail. Two versions are given which run in faster than cubic time. Surprisingly close connections between the Cocke-Kasami-Younger and Earley algorithms are established which reveal that the two algorithms are “almost” identical.
Typed memory management via static capabilities
Authors: Walker David , Crary Karl , Morrisett Greg
Published: October 2002

Region-based memory management is an alternative to standard tracing garbage collection that makes operation such as memory deallocation explicit but verifiably safe. In this article, we present a new compiler intermediate language, called the Capability Language (CL), that supports region-based memory management and enjoys a provably safe type systems. Unlike previous region-based type system, region lifetimes need not be lexically scoped, and yet the language may be checked for safety without complex analyses. Therefore, our type system may be deployed in settings such as extensible operating systems where both the performance and safety of untrusted code is important. The central novelty of the language is the use of static capabilities to specify the permissibility of various operations, such as memory access and deallocation. In order to ensure capabilities are relinquished properly, the type system tracks aliasing information using a form of bounded quantification. Moreover, unlike previous work on region-based type systems, the proof of soundness of our type system is relatively simple, employing only standard syntactic techniques. In order to show how our language may be used in practice, we show how to translate a variant of Tofte and Talpin's high-level type-and-effects system for region-based memory management into our language. When combined with known region inference algorithms, this translation provides a way to compile source-level languages to CL.
The role of commutativity in constraint propagation algorithms
Authors: Apt Krzysztof R.
Published: October 2002

Constraing propagation algorithms form an important part of most of the constraint programming systems. We provide here a simple, yet very general framework that allows us to explain several constraint propagation algorithms in a systematic way. In this framework we proceed in two steps. First, we introduce a generic iteration algorithm on partial orderings and prove its correctness in an abstract setting. Then we instantiate this algorithm with specific partial orderings and functions to obtain specific constraint propagation algorithms. In particular, using the notions commutativity and semi-commutativity, we show that the AC-3, PC-2, DAC, and DPC algorithms for achieving (directional) arc consistency and (directional) path consistency are instances of a single generic algorithm. The work reported here extends and simplifies that of Apt [1999a].
Synthesis of concurrent programs for an atomic read/write model of computation
Authors: Attie Paul C. , Emerson E. Allen
Published: October 2002

Methods for mechanically synthesizing concurrent programs for temporal logic specifications have been proposed by Emerson and Clarke and by Manna and Wolper. An important advantage of these synthesis methods is that they obviate the need to manually compose a program and manually construct a proof of its correctness. A serious drawback of these methods in practice, however, is that they produce concurrent programs for models of computation that are often unrealistic, involving highly centralized system architecture (Manna and Wolper), processes with global information about the system state (Emerson and Clarke), or reactive modules that can read all of their inputs in one atomic step (Anuchitanukul and Manna, and Pnueli and Rosner). Even simple synchronization protocols based on atomic read/write primitives such as Peterson's solution to the mutual exclusion problem have remained outside the scope of practical mechanical synthesis methods. In this paper, we show how to mechanically synthesize in more realistic computational models solutions to synchronization problems. We illustrate the method by synthesizing Peterson's solution to the mutual exclusion problem.
Efficient and correct execution of parallel programs that share memory
Authors: Shasha Dennis , Snir Marc
Published: October 2002

In this paper we consider an optimization problem that arises in the execution of parallel programs on shared-memory multiple-instruction-stream, multiple-data-stream (MIMD) computers. A program on such machines consists of many sequential program segments, each executed by a single processor. These segments interact as they access shared variables. Access to memory is asynchronous, and memory accesses are not necessarily executed in the order they were issued. An execution is correct if it is sequentially consistent: It should seem as if all the instructions were executed sequentially, in an order obtained by interleaving the instruction streams of the processors. Sequential consistency can be enforced by delaying each access to shared memory until the previous access of the same processor has terminated. For performance reasons, however, we want to allow several accesses by the same processor to proceed concurrently. Our analysis finds a minimal set of delays that enforces sequential consistency. The analysis extends to interprocessor synchronization constraints and to code where blocks of operations have to execute atomically. We use a conflict graph similar to that used to schedule transactions in distributed databases. Our graph incorporates the order on operations given by the program text, enabling us to do without locks even when database conflict graphs would suggest that locks are necessary. Our work has implications for the design of multiprocessors; it offers new compiler optimization techniques for parallel languages that support shared variables.
Efficient synchronization of multiprocessors with shared memory
Authors: Kruskal Clyde P. , Rudolph Larry , Snir Marc
Published: October 2002

A new formalism is given for read-modify-write (RMW) synchronization operations. This formalism is used to extend the memory reference combining mechanism introduced in the NYU Ultracomputer, to arbitrary RMW operations. A formal correctness proof of this combining mechanism is given. General requirements for the practicality of combining are discussed. Combining is shown to be practical for many useful memory access operations. This includes memory updates of the form
mem
_
val
:=
mem
_
val op val
, where
op
need not be associative, and a variety of synchronization primitives. The computation involved is shown to be closely related to parallel prefix evaluation.
Automatic data and computation decomposition on distributed memory parallel computers
Authors: Lee Peizong , Kedem Zvi Meir
Published: October 2002

To exploit parallelism on shared memory parallel computers (SMPCs), it is natural to focus on decomposing the computation (mainly by distributing the iterations of the nested Do-Loops). In contrast, on distributed memory parallel computers (DMPCs), the decomposition of computation and the distribution of data must both be handled---in order to balance the computation load and to minimize the migration of data. We propose and validate experimentally a method for handling computations and data synergistically to minimize the overall execution time on DMPCs. The method is based on a number of novel techniques, also presented in this article. The core idea is to rank the "importance" of data arrays in a program and specify some of the dominant. The intuition is that the dominant arrays are the ones whose migration would be the most expensive. Using the correspondence between iteration space mapping vectors and distributed dimensions of the dominant data array in each nested Do-loop, allows us to design algorithms for determining data and computation decompositions at the same time. Based on data distribution, computation decomposition for each nested Do-loop is determined based on either the "owner computes" rule or the "owner stores" rule with respect to the dominant data array. If all temporal dependence relations across iteration partitions are regular, we use tiling to allow pipelining and the overlapping of computation and communication. However, in order to use tiling on DMPCs, we needed to extend the existing techniques for determining tiling vectors and tile sizes, as they were originally suited for SMPCs only. The overall method is illustrated on programs for the 2D heat equation, for the Gaussian elimination with pivoting, and for the 2D fast Fourier transform on a linear processor array and on a 2D processor grid.
Additional methods when using email for teaching
Authors: Malaga Ross A.
Published: October 2002

Providing additional functionality and limiting problems by combining a server-side and client-side approach when teaching with email applications.
Information leakage from optical emanations
Authors: Loughry Joe , Umphress David A.
Published: October 2002

A previously unknown form of compromising emanations has been discovered. LED status indicators on data communication equipment, under certain conditions, are shown to carry a modulated optical signal that is significantly correlated with information being processed by the device. Physical access is not required; the attacker gains access to all data going through the device, including plaintext in the case of data encryption systems. Experiments show that it is possible to intercept data under realistic conditions at a considerable distance. Many different sorts of devices, including modems and Internet Protocol routers, were found to be vulnerable. A taxonomy of compromising optical emanations is developed, and design changes are described that will successfully block this kind of "Optical Tempest" attack.
Logisim
Authors: Burch Carl
Published: October 2002

Logisim enables students in introductory courses to design and simulate logic circuits. The program's design emphasizes simplicity of use, with a secondary goal of enabling design of sophisticated circuits. This motivates a two-tiered system, where users can move to the second tier by selecting a menu option.Users draw circuits of logic gates using the toolbox model popular in drawing programs. The circuit automatically propagates circuit values through the circuit; by selecting the appropriate tool, users can toggle switches to see how the circuit behaves in other situations. In the advanced tier, the user can treat circuits as black boxes within larger circuits, enabling the simulation of hierarchical designs. The author has successfully drawn and tested a simple 8 bit CPU using the program.The program has proven useful in a variety of introductory courses, from a nonmajors survey course to a sophomore-level systems course. Students find Logisim simple to follow, and find the laboratories designed around it useful in reinforcing the circuit concepts from class.In this article, we identify and compare a variety of systems similar to Logisim, we explore Logisim's features in detail, and we examine its use in class assignments.
The KScalar simulator
Authors: Moure J. C. , Rexachs Dolores I. , Luque Emilio
Published: October 2002

Modern processors increase their performance with complex microarchitectural mechanisms, which makes them more and more difficult to understand and evaluate. KScalar is a graphical simulation tool that facilitates the study of such processors. It allows students to analyze the performance behavior of a wide range of processor microarchitectures: from a very simple in-order, scalar pipeline, to a detailed out-of-order, superscalar pipeline with non-blocking caches, speculative execution, and complex branch prediction. The simulator interprets executables for the Alpha AXP instruction set: from very short program fragments to large applications. The object's program execution may be simulated in varying levels of detail: either cycle-by-cycle, observing all the pipeline events that determine processor performance, or million cycles at once, taking statistics of the main performance issues.Instructors may use KScalar in several ways. First, it may be used to provide demonstrations in lectures or online learning environments. Second, it allows students to investigate the characteristics of specific processor microarchitectures as practical short assignments associated to a lecture course. Third, students may undertake major projects involving the optimization of real programs at the software-hardware interface, or involving the optimization of a processor microarchitecture for a given application workload.A preliminary version of KScalar has been successfully used in several lecture courses during the last two years in the University Autónoma of Barcelona. It runs on a x86/Linux/KDE system. The graphical interface has been developed using the KDE and QT libraries. The simulator engine running behind the graphical interface is a heavily-modified version of SimpleScalar. KScalar code is available under the terms of the GNU and SimpleScalar General Public License
Cut-and-paste editing of multiresolution surfaces
Authors: Biermann Henning , Martin Ioana , Bernardini Fausto , Zorin Denis
Published: October 2002

Cutting and pasting to combine different elements into a common structure are widely used operations that have been successfully adapted to many media types. Surface design could also benefit from the availability of a general, robust, and efficient cut-and-paste tool, especially during the initial stages of design when a large space of alternatives needs to be explored. Techniques to support cut-and-paste operations for surfaces have been proposed in the past, but have been of limited usefulness due to constraints on the type of shapes supported and the lack of real-time interaction. In this paper, we describe a set of algorithms based on multiresolution subdivision surfaces that perform at interactive rates and enable intuitive cut-and-paste operations.
Progressive lossless compression of arbitrary simplicial complexes
Authors: Gandoin Pierre-Marie , Devillers Olivier
Published: October 2002

Efficient algorithms for compressing geometric data have been widely developed in the recent years, but they are mainly designed for closed polyhedral surfaces which are
manifold
or "nearly manifold". We propose here a
progressive
geometry compression scheme which can handle manifold models as well as "triangle soups" and 3D tetrahedral meshes. The method is lossless when the decompression is complete which is extremely important in some domains such as medical or finite element.While most existing methods enumerate the vertices of the mesh in an order depending on the connectivity, we use a kd-tree technique [Devillers and Gandoin 2000] which does not depend on the connectivity. Then we compute a compatible sequence of meshes which can be encoded using edge expansion [Hoppe et al. 1993] and vertex split [Popović and Hoppe 1997].The main contributions of this paper are: the idea of using the kd-tree encoding of the geometry to drive the construction of a sequence of meshes, an improved coding of the edge expansion and vertex split since the vertices to split are implicitly defined, a prediction scheme which reduces the code for simplices incident to the split vertex, and a new generalization of the edge expansion operation to tetrahedral meshes.
Homomorphic factorization of BRDF-based lighting computation
Authors: Latta Lutz , Kolb Andreas
Published: October 2002

Several techniques have been developed to approximate Bidirectional Reflectance Distribution Functions (BRDF) with acceptable quality and performance for realtime applications. The recently published
Homomorphic Factorization
by McCool et al. is a general approximation approach that can be used with various setups and for different quality requirements.In this paper we propose a new technique based on the Homomorphic Factorization. Instead of approximating the BRDF, our technique factorizes the full lighting computation of an isotropic BRDF in a global illumination scenario. With this method materials in complex lighting situations can be simulated with only two textures by using commonly available computation capabilities of current graphics hardware.The new technique can also be considered as a generalized approach to several environment map prefiltering techniques. Existing prefiltering techniques are usually limited to specific BRDFs or require advanced hardware capabilities like 3D texturing. With the factorization only common 2D textures are required.
Handling irreducible loops
Authors: Unger Sebastian , Mueller Frank
Published: October 2002

This paper addresses the question of how to handle irreducible regions during optimization, which has become even more relevant for contemporary processors since recent VLIW-like architectures highly rely on instruction scheduling. The contributions of this paper are twofold. First, a method of optimized node splitting to transform irreducible regions of control flow into reducible regions is formally defined and its correctness is shown. This method is superior to approaches previously published since it reduces the number of replicated nodes by comparison. Second, three methods that handle regions of irreducible control flow are evaluated with respect to their impact on compiler optimizations. First, traditional node splitting is evaluated. Second, optimized node splitting is implemented. Third, DJ-Graphs are utilized to recognize nesting of irreducible (and reducible) loops and apply common loop optimizations extended for irreducible loops. Experiments compare the performance of these approaches with unrecognized irreducible loops that cannot be subject to loop optimizations, which is typical for contemporary compilers. Measurements show improvements of 1 to 40% for these methods of handling irreducible loops over the unoptimized case. Optimized node splitting may be chosen to retrofit existing compilers since it has the advantage that it only requires few changes to an optimizing compiler while limiting the code growth of compiled programs compared to traditional node splitting. Recognizing loops via DJ-Graphs should be chosen for new compiler developments since it requires more changes to the optimizer but does not significantly change the code size of compiled programs while yielding comparable improvements. Handling irreducible loops should even yield more benefits for exploiting instruction-level parallelism of modern architectures in the context of global instruction scheduling and optimization techniques that may introduce irreducible loops, such as enhanced modulo scheduling.
Paradoxes in distributed decisions on optimal load balancing for networks of homogeneous computers
Authors: Kameda Hisao , Pourtallier Odile
Published: October 2002

In completely symmetric systems that have homogeneous nodes (hosts, computers, or processors) with identical arrival processes, an optimal static load balancing scheme does not involve the forwarding of jobs among nodes. Using an appropriate analytic model of a distributed computer system, we examine the following three decision schemes for load balancing: completely distributed, intermediately distributed, and completely centralized. We show that there is no forwarding of jobs in the completely centralized and completely distributed schemes, but that in an intermediately distributed decision scheme, mutual forwarding of jobs among nodes is possible, leading to degradation in system performance for every decision maker. This result appears paradoxical, because by adding communication capacity to the system for the sharing of jobs between nodes, the overall system performance is degraded. We characterize conditions under which such paradoxical behavior occurs, and we give examples in which the degradation of performance may increase without bound. We show that the degradation reduces and finally disappears in the limit as the intermediately distributed decision scheme tends to a completely distributed one.
UST/DME
Authors: Tsao Chung-wen Albert , Koh Cheng-kok
Published: October 2002

In this article, we propose new approaches for solving the useful-skew tree (UST) routing problem [Xi and Dai 1997]: clock routing subject to general skew constraints. The clock layout synthesis engine of our UST algorithms is based on the deferred-merge embedding (DME) paradigm for the zero-skew tree (ZST) [Edahiro 1992; Chao et al. 1992] and bounded-skew tree (BST) [Cong and Koh 1995; Huang et al. 1995; Kahng and Tsao 1997; Cong et al. 1998] routings; hence, the names UST/DME and Greedy-UST/DME for our UST algorithms. Our novel contribution is that we simultaneously perform skew scheduling and tree routing so that each local skew range is incrementally refined to a skew value that minimizes the wirelength increase during the bottom-up merging phase of DME. As a result, not only is the skew schedule feasible, but also the wirelength increase is minimized at each merging step of clock tree construction. The experimental results show very encouraging improvement over the previous BST/DME algorithm on three ISCAS89 benchmarks under general skew constraints in terms of total routing wirelength.
Algorithm 818
Authors: Duff Iain S. , Vömel Christof
Published: October 2002

The Basic Linear Algebra Subprograms for sparse matrices (Sparse BLAS) as defined by the BLAS Technical Forum are a set of routines providing basic operations for sparse matrices and vectors. A principal goal of the Sparse BLAS standard is to aid in the development of iterative solvers for large sparse linear systems by specifying on the one hand interfaces for a high-level description of vector and matrix operations for the algorithm developer and on the other hand leaving enough freedom for vendors to provide the most efficient implementation of the underlying algorithms for their specific architectures.The Sparse BLAS standard defines interfaces and bindings for the three target languages: C, Fortran 77 and Fortran 95. We describe here our Fortran 95 implementation intended as a reference model for the Sparse BLAS. We identify the underlying complex issues of the representation and the handling of sparse matrices and give suggestions to other implementors of how to address them.
Cooperative visual manipulation of music notation
Authors: Bellini P. , Nesi P. , Spinu M. B.
Published: October 2002

As computer technologies and their potential emerging applications spread out, new needs have been detected for computer-based applications of music; cooperative music notation editing both in orchestras and music schools is one of them. This article is the only public document describing the details of cooperative work on music notation of MOODS (Music Object Oriented Distributed System). MOODS is a synchronous real-time cooperative editor for music scores. Its architecture includes mechanisms for troubleshooting conflicts in real-time, managing histories of commands and versioning, and for performing selective undo. The system also includes specific solutions in order to control the editing on the account of editing permission profiles. The most important aspects of MOODS associated with cooperative work on music notation scores are reported herein. The article highlights the general problems of cooperative systems and provides rationales for the solutions, which were found to build MOODS. The MOODS system has been implemented and validated thanks to the endeavor of several musicians in orchestras, music schools, and project partners. A prototype has been demonstrated in public at the Scala Theatre in Milan, Italy.