bluuebunny/crossref_metadata_2025 huggingface dataset:
Non-Linear Characteristics in the Dynamic Responses of Seated Subjects Exposed to Vertical Whole-Body Vibration
Authors: Matsumoto Yasunao , Griffin Michael J.
Published: October 2002

The effect of the magnitude of vertical vibration on the dynamic response of the seated human body has been investigated. Eight male subjects were exposed to random vibration in the 0.5 to 20 Hz frequency range at five magnitudes: 0.125, 0.25, 0.5, 1.0 and 2.0 ms−2 r.m.s. The dynamic responses of the body were measured at eight locations: at the first, fifth, and tenth thoracic vertebrae (T1, T5, T10), at the first, third, and fifth lumbar vertebrae (L1, L3, L5) and at the pelvis (the posterior-superior iliac spine). At each location, the motions on the body surface were measured in the three orthogonal axes within the sagittal plane (i.e., the vertical, fore-and-aft, and pitch axes). The force at the seat surface was also measured. Frequency response functions (i.e., transmissibilities and apparent mass) were used to represent the responses of the body. Non-linear characteristics were observed in the apparent mass and in the transmissibilities to most measurement locations. Resonance frequencies in the frequency response functions decreased with increases in the vibration magnitude (e.g. for the vertical transmissibility to L3, a reduction from 6.25 to 4.75 Hz when the vibration magnitude increased from 0.125 to 2.0 ms−2 r.m.s.). The transmission of vibration within the spine also showed some evidence of a non-linear characteristic. It can be concluded from this study that the dynamic responses of seated subjects are clearly non-linear with respect to vibration magnitude, whereas previous studies have reported inconsistent conclusions. More understanding of the dependence on vibration magnitude of both the dynamic responses of the soft tissues of the body and the muscle activity (voluntary and involuntary) is required to identify the causes of the non-linear characteristics observed in this study.
Time Frequency Characteristics of the Vibroacoustic Signal of Hydrodynamic Cavitation
Authors: Wen Yumei , Henry Manus
Published: September 2002

A theoretical analysis and experimental results are presented of the time-frequency characteristics of hydrodynamic cavitation signals. Because of the limitation of the frequency bandwidth of the data acquisition system and the random nature of cavity collapses, the signal consists of transient burst waveforms. The acoustic pulses from collapses in close time proximity mix together and form transient oscillatory bursts. The local oscillation frequency of a burst is related to either the time duration between burst collapses or the cut-off frequency of the system. These results enable the identification and detection of individual cavitation events by the time-frequency characteristics in the vibroacoustic signal.
Design of an Adaptive Vibration Absorber to Reduce Electrical Transformer Structural Vibration
Authors: Hill Simon G. , Snyder Scott D.
Published: September 2002

This paper considers the design of a vibration absorber to reduce structural vibration at multiple frequencies, with an enlarged bandwidth control at these target frequencies. While the basic absorber is a passive device a control system has been added to facilitate tuning, effectively giving the combination of a passive and active device, which leads to far greater stability and robustness. Experimental results demonstrating the effectiveness of the absorber are also described.
Lancaster’s Method of Damping Identification Revisited
Authors: Adhikari Sondipon
Published: September 2002

Identification of damping is an active area of research in structural dynamics. In one of the earliest works, Lancaster [1] proposed a method to identify the viscous damping matrix from measured natural frequencies and mode shapes. His method requires the modes to be normalized in a particular way, which in turn a priori needs the very same viscous damping matrix. A method, based on the poles and residues of the measured transfer functions, has been proposed to overcome this basic difficulty associated with Lancaster’s method. This approach is then extended to a class of nonviscously damped systems where the damping forces depend on the past history of the velocities via convolution integrals over some kernel functions. Suitable numerical examples are given to illustrate the modified Lancaster’s method developed here.
H 2 Optimization of the Three-Element Type Dynamic Vibration Absorbers
Authors: Asami Toshihiko , Nishihara Osamu
Published: September 2002

The dynamic vibration absorber (DVA) is a passive vibration control device which is attached to a vibrating body (called a primary system) subjected to exciting force or motion. In this paper, we will discuss an optimization problem of the three-element type DVA on the basis of the H2 optimization criterion. The objective of the H2 optimization is to reduce the total vibration energy of the system for overall frequencies; the total area under the power spectrum response curve is minimized in this criterion. If the system is subjected to random excitation instead of sinusoidal excitation, then the H2 optimization is probably more desirable than the popular H∞ optimization. In the past decade there has been increasing interest in the three-element type DVA. However, most previous studies on this type of DVA were based on the H∞ optimization design, and no one has been able to find the algebraic solution as of yet. We found a closed-form exact solution for a special case where the primary system has no damping. Furthermore, the general case solution including the damped primary system is presented in the form of a numerical solution. The optimum parameters obtained here are compared to those of the conventional Voigt type DVA. They are also compared to other optimum parameters based on the H∞ criterion.
Adaptive Order Tracking Technique Using Recursive Least-Square Algorithm
Authors: Bai Mingsian R. , Jeng Jihjau , Chen Chingyu
Published: September 2002

Order tracking technique is one of the important tools for diagnosis of rotating machinery. Conventional methods of order tracking are primarily based on Fourier analysis with reference to shaft speed. Resampling is generally required in the fast Fourier transform (FFT)-based methods to compromise between time and frequency resolution for varying shaft speeds. Conventional methods suffer from a number of shortcomings. In particular, smearing problems arise when closely spaced orders or crossing orders are present. Conventional methods also are ineffective for the applications involving multiple independent shaft speeds. This paper presents an adaptive order tracking technique based on the Recursive Least-Squares (RLS) algorithm to overcome the problems encountered in conventional methods. In the proposed method, the problem is treated as the tracking of frequency-varying bandpass signals. Order amplitudes can be calculated with high resolution by using the proposed method in real-time fashion. The RLS order tracking technique is applicable whether it is a single-axle or multi-axle system.
Torsional Vibration of Non-Uniform Shafts Carrying an Arbitrary Number of Rigid Disks
Authors: Qiao H. , Li Q. S. , Li G. Q.
Published: September 2002

A new exact approach for the analysis of torsional vibration of a non-uniform shaft carrying an arbitrary number of rigid disks is presented. The exact solutions for non-uniform shafts with arbitrary distribution of torsional stiffness or mass polar moment of inertia are obtained for several important cases. The fundamental solutions developed in this paper lead to a single frequency equation for a non-uniform shaft with classical or non-classical boundary conditions and carrying an arbitrary number of rigid disks.
Using Genetic Algorithms to Set Target Values for Engineering Characteristics in the House of Quality
Authors: Brackin Patricia , Colton Jonathan S.
Published: September 2002

As part of a strategy for obtaining preliminary design specifications from the House of Quality, genetic algorithms are used to generate and optimize preliminary design specifications for an automotive case study. This paper describes the House of Quality for an automotive case study. In addition, the genetic algorithm chosen, the genetic coding, the methods used for mutation and reproduction, and the fitness and penalty functions are described. Methods for determining convergence are examined. Finally, test results show that the genetic algorithm produces reasonable preliminary design specifications.
A Region Based Method to Automated Design of Multi-Piece Molds with Application to Rapid Tooling
Authors: Chen Yong , Rosen David W.
Published: September 2002

Particularly for rapid tooling applications, delivering prototype parts with turn-around times of less than two weeks requires fast, proven mold design methods. We present a region-based approach to automated mold design that is suitable for simple two-piece molds (consisting of core and cavity), as well as molds with many additional moving sections. In our region-based approach, part faces are partitioned into regions, each of which can be formed by a single mold piece. The basic elements of our approach are concave regions (generalized pockets) and convex faces since these elements are central to the identification of regions. This paper focuses on the initial steps of automated mold design, including a problem formulation, methods for identifying the basic elements from part faces, and combining them into regions. By seeking to minimize the number of mold pieces, different partitions of faces into regions are explored until the smallest number of regions is found. During this process, a linear programming problem is adopted for finding a satisfactory parting direction of a region. Algorithms are presented for the region generating and combining process. Our approach is illustrated with several examples of industrial injection molded parts.
Producing Follower Motions Through Their Digitized Cam Contours
Authors: Tsay Der-Min , Huang Meng-Hung , Ho Hui-Chun
Published: September 2002

A computing procedure that can be used to generate follower motions with a higher degree of accuracy by using their digitized 2-D cam surfaces is presented. Based on the geometric relationships at the contact point between a planar cam and its follower, the reverse functions that can be solved to find the follower motion of the cam-follower mechanism are established. To approximate the digitized cam surfaces and to create their derivatives required in determining the follower motions, a least squares periodic B-spline approximation is also introduced. In comparison with analytical results obtained from a theoretical design, the procedure is verified for its accuracy and reliability. Furthermore, by using the cam surface data points taken from a CMM, a practical example is given to show the effectiveness and usefulness of the proposed techniques.
Identification and Characterization of Regular Surfaces from Unorganized Points by Normal Sensitivity Analysis
Authors: Huang Jianbing , Menq Chia-Hsiang
Published: September 2002

In this paper, the concept of free motion subspace is introduced and utilized to characterize the special kinematic properties of regular surfaces, including planes, natural quadrics, and regular swept surfaces. Based on the concept, a general approach is developed to automatically identify the surface type and calculate the associated geometric parameters of an unknown surface from unorganized measurement points. In the approach, a normal sensitivity matrix, that characterizes the normal perturbation of surface points under differential motions, is derived. With the normal sensitivity matrix, it is shown that the free motion subspace of a surface can be determined through a regular eigen analysis. From the identified free motion subspace, the surface type of a regular surface can be determined and its geometric parameters can be simultaneously computed. An algorithm that identifies the free motion subspace of an unknown surface from its unorganized sample points has been implemented. Experiments are carried out to investigate the robustness and efficiency of the developed algorithm. The developed algorithm can be used to solve various problems including geometric primitive classification and parameter estimation, regular swept surface reconstruction, geometric constraint recognition and multi-view data registration. Integrated with state-of-art segmentation techniques, the proposed method can be used for object recognition, robot vision, and reverse engineering.
Influence of velocity profile nonuniformity on minor losses for flow exiting thermoacoustic heat exchangers (L)
Authors: Wakeland Ray Scott , Keolian Robert M.
Published: October 2002

Nonuniform, time-dependent velocity profiles for laminar oscillating flow are employed in calculating effective minor loss exit coefficients. The results could represent an improvement over the Borda–Carnot formula for calculating flow losses at the exit from heat exchangers in thermoacoustic devices, since the Borda–Carnot formula assumes uniform velocity across a flow cross section. Results are presented for parallel plate and circular tube geometries.
Berger in retrospect: effect of varied weight training programmes on strength
Authors: Carpinelli R N
Published: September 2002

The evidence that multiple sets of exercise are superior to a single set for maximal strength gains, as suggested by Berger in 1962, is reviewed. The validity and practical significance of Berger's strength training study are questioned. Well controlled, methodologically sound studies that minimise confounding variables are required to support the hypothesis that multiple sets of exercise elicit superior gains in strength.
Extensional exhumation of a high-pressure granulite terrane in Payer Land, Greenland Caledonides: structural, petrologic, and geochronologic evidence from metapelites
Authors: Gilotti Jane A , Elvevold Synnøve
Published: September 2002

The Payer Land gneiss complex is unique among the mostly amphibolite-facies, mid-crustal gneiss complexes in the East Greenland Caledonides due to its well-preserved, regional high-pressure (HP) granulite-facies metamorphism. High-pressure  high-temperature (HPHT) assemblages are recognized in mafic, ultramafic, granitic, and metasedimentary lithologies. Anatectic metapelites contain the assemblage garnet + kyanite + K-feldspar + antiperthite (exsolved ternary feldspar) + quartz ± biotite ± rutile and record approximately the same peak metamorphic conditions (pressure (P) = 1.41.5 GPa, temperature (T) = 800850°C) as those of the neighboring mafic HP granulites. The HP granulite-facies metamorphism is Caledonian based on in situ UThPb electron microprobe dating of monazite from two samples of the aluminous paragneiss. The monazites are found along garnetkyanite phase boundaries, as inclusions in garnet and kyanite, and within small leucocratic melt pods (K-feldspar + plagioclase + kyanite ± garnet) within the HPHT paragneisses. Mylonitic equivalents of the metapelites contain a detrital monazite age signature that suggests the Payer Land paragneisses correlate with other Mesoproterozoic metasedimentary sequences in the area. The gneisses form a metamorphic core complex that is separated from the overlying low-grade sedimentary rocks of the Neoproterozoic Eleonore Bay Supergroup by an extensional detachment. This newly recognized Payer Land detachment is part of a system of prominent extensional faults located in the southern half of the Greenland Caledonides (i.e., south of 76°N). The HP granulites preserve the deepest level of crust exposed in this southern segment of the orogen and attest to significant crustal thickening.
A multistage magmatic history for the genesis of the Orford ophiolite (Quebec, Canada): a study of the Mont Chagnon massif
Authors: Huot François , Hébert Réjean , Turcotte Bruno
Published: September 2002

This paper concerns the petrogenesis of the 504 ± 3 Ma Mont Chagnon massif, the southern extension of the Orford ophiolite in the Quebec Appalachians. The evolution of this massif is summarized in three stages marked by different magmatic series. In the Late Cambrian, the onset of southeastern subduction of the Iapetus basin generated an immature oceanic island arc made up of light rare-earth-element-depleted tholeiites, now preserved in the massif as a portion of the intrusive crustal unit, the dyke complex, and part of the lower volcanic unit. A phase of arc splitting, and concomitant partial erosion of the crustal section, was shortly followed by the eruption of rhyolite genetically related to felsic and low-Ti dykes, and trondhjemite. The geochemistry of these magmas bear some similarities with boninitic series. We believe these liquids derived from the partial melting of the Iapetus amphibolitized oceanic crust, with that of its Laurentian-derived sediments and nearby peridotite, either found as a trapped sliver above the subducting slab or as the slab itself. The final stage, preserved in the massif as a part of the intrusive section, the upper volcanic rocks, and the late-stage dykes, represents the back-arc opening. An ocean-island component is involved in the back-arc related petrogenetic processes, producing magmas with compositions intermediate between arc tholeiites and enriched back-arc basin basalts. This is the first report that the Iapetus basin was locally closing as early as Late Cambrian in the southern Quebec area.
Products of 2.652.58 Ga orogenesis in the Slave Province correlated with Slave  Northern Cordillera Lithospheric Evolution (SNORCLE) seismic reflection patterns
Authors: van der Velden Arie J , Cook Frederick A
Published: September 2002

Reflection patterns along Lithoprobe Slave  Northern Cordillera Lithospheric Evolution (SNORCLE) seismic reflection line 1 in the southwestern Slave Province are interpreted as products of tectonic wedging during late Archean lithospheric convergence. The interpretation is aided by application of new seismic imaging techniques, by correlation of upper crustal reflection patterns to known geology, and by a comparison of lithospheric reflection patterns to similar convergent zones elsewhere. In the Yellowknife area, reflection patterns consist of (1) east-dipping reflections at 1214 s that project into the upper mantle, (2) a wedge-shaped body in the lower crust with an east-dipping reflection fabric that is truncated on the west by (3) a series of west-dipping reflections that outline thrust-and-fold structures in the upper crust. The similarity of these reflection patterns to those of the Proterozoic Fort Simpson  Hottah collision zone ~300 km to the west provides support for the interpretation that reflection patterns beneath the Slave Province are also products of collisional tectonics. Rocks within the Slave Province preserve evidence of a ~2.652.58 Ga pan-Slave orogenic event, in which the >2.9 Ga Central Slave Basement collided with the ~2.7 Ga juvenile eastern Slave Province. Their suture is interpreted to be a west-dipping surface at 45 s (1215 km) beneath Yellowknife and to project to the surface east of the profile. In the lower crust and upper mantle, east-dipping reflections are interpreted to delineate a coeval subduction zone and accretionary wedge. The upper crustal thrust-and-fold structures are likely linked to gold-bearing shear zones at Yellowknife. These results provide tantalizing evidence that processes similar to those of modern convergent zones were operational at 2.652.58 Ga.
Physical and chemical properties of the Sulphur Mountain thermal springs, Banff National Park, and implications for endangered snails
Authors: Grasby Stephen E , Lepitzki Dwayne A.W
Published: September 2002

Nine thermal springs, in three groups, occur along the flank of Sulphur Mountain in Banff National Park. The principal recharge zone is suggested to be above 2000 m elevation on Mount Rundle, circulation depths are estimated to be 3.2 ± 0.6 km, and discharge is focused along the Sulphur Mountain Thrust. Springs show constant temperature and total dissolved solids load throughout the winter, whereas both drop in association with spring snowmelt. The degree and timing of temperature drops are a function of elevation, with the highest springs showing the earliest and most significant temperature drop. The highest elevation springs also show the greatest seasonal variability in water chemistry. Unusual seasonal flow stoppages of these springs are related to extreme low precipitation years. The biogeochemistry of the thermal springs and population fluctuations of the endemic and endangered Banff springs snail (Physella johnsoni) are strongly related to seasonal variability in flow rates. Changes in redox conditions associated with an influx of shallow groundwater during spring snowmelt negatively impact the microbial community that forms a principal food supply for the snail.
The concurrency workbench
Authors: Cleaveland Rance , Parrow Joachim , Steffen Bernhard
Published: October 2002

The Concurrency Workbench is an automated tool for analyzing networks of finite-state processes expressed in Milner's Calculus of Communicating Systems. Its key feature is its breadth: a variety of different verification methods, including equivalence checking, preorder checking, and model checking, are supported for several different process semantics. One experience from our work is that a large number of interesting verification methods can be formulated as combinations of a small number of primitive algorithms. The Workbench has been applied to the verification of communications protocols and mutual exclusion algorithms and has proven a valuable aid in teaching and research.
Software merge
Authors: Berzins Valdis
Published: October 2002

We present a language-independent semantic model of the process of combining changes to programs. This model extends the domains used in denotational semantics (complete partial orders) to Boolean algebras, and represents incompatible modifications as well as compatible extensions. The model is used to define the intended semantics of change-merging operations on programs and to establish some general properties of software merging. We determine conditions under which changes to subprograms of a software system can be merged independently and illustrate cases where this is not possible.
DIB—a distributed implementation of backtracking
Authors: Finkel Raphael , Manber Udi
Published: October 2002

DIB is a general-purpose package that allows a wide range of applications such as recursive backtrack, branch and bound, and alpha-beta search to be implemented on a multicomputer. It is very easy to use. The application program needs to specify only the root of the recursion tree, the computation to be performed at each node, and how to generate children at each node. In addition, the application program may optionally specify how to synthesize values of tree nodes from their children's values and how to disseminate information (such as bounds) either globally or locally in the tree. DIB uses a distributed algorithm, transparent to the application programmer, that divides the problem into subproblems and dynamically allocates them to any number of (potentially nonhomogeneous) machines. This algorithm requires only minimal support from the distributed operating system. DIB can recover from failures of machines even if they are not detected. DIB currently runs on the Crystal multicomputer at the University of Wisconsin-Madison. Many applications have been implemented quite easily, including exhaustive traversal (
N
queens, knight's tour, negamax tree evaluation), branch and bound (traveling salesman) and alpha-beta search (the game of NIM). Speedup is excellent for exhaustive traversal and quite good for branch and bound.
Polymorphic typing of variables and references
Authors: Smith Geoffrey , Volpano Dennis
Published: October 2002

In this article we consider the polymorphic type checking of an imperative language. Our language contains
variables
, first-class
references
(pointers), and first-class functions. Variables, as in traditional imperative languages, are implicitly dereferenced, and their addresses (
L
-values) are not first-class values. Variables are easier to type check than references and, in many cases, lead to more general polymorphic types. We present a polymorphic type system for our language and prove that it is sound. Programs that use variables sometimes require weak types, as in Tofte's type system for Standard ML, but such weak types arise far less frequently with variables than with references
A task- and data-parallel programming language based on shared objects
Authors: Ben Hassen Saniya , Bal Henri E. , Jacobs Ceriel J. H.
Published: October 2002

Many programming languages support either task parallelism, but few languages provide a uniform framework for writing applications that need both types of parallelism or data parallelism. We present a programming language and system that integrates task and data parallelism using shared objects. Shared objects may be stored on one processor or may be replicated. Objects may also be partitioned and distributed on several processors.Task parallelism is achieved by forking processes remotely and have them communicate and synchronize through objects. Data parallelism is achieved by executing operations on partitioned objects in parallel. Writing task-and data-parallel applications with shared objects has several advantages. Programmers use the objects as if they were stored in a memory common to all processors. On distributed-memory machines, if objects are remote, replicated, or partitioned, the system takes care of many low-level details such as data transfers and consistency semantics. In this article, we show how to write task-and data-parallel programs with our shared object model. We also desribe a portable implementation of the model. To assess the performance of the system, we wrote several applications that use task and data parallelism and excuted them on a collection of Pentium Pros connected by Myrinet. The performance of these applications is also discussed in this article.
Sharing and groundness dependencies in logic programs
Authors: Codish Michael , Søndergaard Harald , Stuckey Peter J.
Published: October 2002

We investigate Jacobs and Langen's Sharing domain, introduced for the analysis of variable sharing in logic programs, and show that it is isomorphic to Marriott and Søndergaard's Pos domain, introduced for the analysis of groundness dependencies. Our key idea is to view the sets of variables in a Sharing domain element as the models of a corresponding Boolean function. This leads to a recasting of sharing analysis in terms of the property of “not being affected by the binding of a single variable.” Such an “unaffectedness dependency” analysis has close connections with groundness dependency analysis using positive Boolean functions. This new view improves our understanding of sharing analysis, and leads to an elegant expression of its combination with groundness dependency analysis based on the reduced product of Sharing and Pos. It also opens up new avenues for the efficient implementation of sharing analysis, for example using reduced order binary decision diagrams, as well as efficient implementation of the reduced product, using domain factorizations.
Type-based analysis of uncaught exceptions
Authors: Leroy Xavier , Pessaux François
Published: October 2002

This article presents a program analysis to estimate uncaught exceptions in ML programs. This analysis relies on unification-based type inference in a nonstandard type system, using rows to approximate both the flow of escaping exceptions (a la effect systems) and the flow of result values (a la control-flow analyses). The resulting analysis is efficient and precise; in particular, arguments carried by exceptions are accurately handled.
Fusion-based register allocation
Authors: Lueh Guei-Yuan , Gross Thomas , Adl-Tabatabai Ali-Reza
Published: October 2002

The register allocation phase of a compiler maps live ranges of a program to registers. If there are more candidates than there are physical registers, the register allocator must spill a live range (the home location is in memory) or split a live range (the live range occupies multiple locations). One of the challenges for a register allocator is to deal with spilling and splitting together. Fusion-based register allocation uses the structure of the program to make splitting and spilling decisions, with the goal to move overhead operations to infrequently executed parts of a program. The basic idea of fusion-based register allocation is to build up the interference graph. Starting with some base region (e.g., a basic block, a loop), the register allocator adds basic blocks to the region and incrementallly builds the interference graph. When there are more live ranges than registers, the register allocator selects live ranges to split; these live ranges are split along the edge that was most recently added to the region. This article describes fusion-based register allocation in detail and compares it with other approaches to register allocation. For programs from the SPEC92 suite, fusion-based register allocation can improve the execution time (of optimized programs, for the MIPS architecture) by up to 8.4% over Chaitin-style register allocation.
Incremental Parsing
Authors: Ghezzi Carlo , Mandrioli Dino
Published: October 2002

An incremental parser is a device which is able to perform syntax analysis in an incremental way, avoiding complete reparsing of a program after each modification. The incremental parser presented extends the conventional LR parsing algorithm and its performance is compared with that of a conventional parser. Suggestions for an implementation and possible extensions to other parsing methods are also discussed.
And/Or Programs: A New Approach to Structured Programming
Authors: Harel David
Published: October 2002

A simple tree-like programming/specification language is presented. The central idea is the dividing of conventional programming constructs into the two classes of
and
and
or
subgoaling, the subgoal tree itself constituting the program. Programs written in the language can, in general, be both nondeterministic and parallel. The syntax and semantics of the language are defined, a method for verifying programs written in it is described, and the practical significance of programming in the language assessed. Finally, some directions for further research are indicated.
On the performance of balanced hashing functions when the keys are not equiprobable
Authors: Papadimitriou Christos H. , Bernstein Philip A.
Published: October 2002

The cost (expected number of accesses per retrieval) of hashing functions is examined without the assumption that it is equally probable for all keys to be present in the table. It is shown that the obvious strategy—trying to balance the sums of probabilities of the keys mapped to any given address—may be suboptimal; however, the difference from the exactly optimal distribution cannot be large.
The Design and Application of a Retargetable Peephole Optimizer
Authors: Davidson Jack W. , Fraser Christopher W.
Published: October 2002

Peephole optimizers improve object code by replacing certain sequences of instructions with better sequences. This paper describes PO, a peephole optimizer that uses a symbolic machine description to simulate pairs of adjacent instructions, replacing them, where possible, with an equivalent single instruction. As a result of this organization, PO is machine independent and can be described formally and concisely: when PO is finished, no instruction, and no pair of adjacent instructions, can be replaced with a cheaper single instruction that has the same effect. This thoroughness allows PO to relieve code generators of much case analysis; for example, they might produce only load/add-register sequences and rely on PO to, where possible, discard them in favor or add-memory, add-immediate, or increment instructions. Experiments indicate that naive code generators can give good code if used with PO.
Sets and constraint logic programming
Authors: Dovier Agostino , Piazza Carla , Pontelli Enrico , Rossi Gianfranco
Published: October 2002

In this paper we present a study of the problem of handling constraints made by conjunctions of positive and negative literals based on the predicate symbols =, ∈,∪ and || (i.e., disjointness of two sets) in a (hybrid) universe of
finite sets
. We also review and compare the main techniques considered to represent finite sets in the context of logic languages. The resulting contraint algorithms are embedded in a Constraint Logic Programming (CLP) language which provides finite sets—along with basic set-theoretic operations—as first-class objects of the language. The language—called CLP(
SET
)—is an instance of the general CLP framework, and as such it inherits all the general features and theoretical results of this scheme. We provide, through programming examples, a taste of the expressive power offered by programming in CLP(
SET
).
Scheduling time-constrained instructions on pipelined processors
Authors: Leung Allen , Palem Krishna V. , Pnueli Amir
Published: October 2002

In this work we investigate the problem of scheduling instructions on idealized microprocessors with multiple pipelines, in the presence of precedence constraints, release-times, deadlines, and latency constraints. A latency of

l
ij

specifies that there must be at least

l
ij

time-steps between the completion time of instruction
i
and the start time of instruction
j
. A latency of

l
ij

=−1 can be used to specify that
j
may be scheduled concurrently with
i
but not earlier. We present a generic algorithm that runs in
O
(
n
2
log
n
α(
n
)+
ne
) time, given
n
instructions and
e
edges in the precedence DAG, where α(
n
) is the functional inverse of the Ackermann function. Our algorithm can be used to construct feasible schedules for various classes of instances, including instances with the following configurations: (1) one pipeline, with individual release-times and deadlines and where the latencies between instructions are restricted to 0 and 1; (2)
m
pipelines, with individual release-times and deadlines, and monotone-interval order precedences; (3) two pipelines with latencies of −1 or 0, and release-times and deadlines; (4) one pipeline, latencies of 0 or 1 and individual processing times that are at least one; (5)
m
pipelines, intree precedences, constant latencies, and deadlines; (6)
m
pipelines, outtree precedences, constant latencies, and release-times. For instances with deadlines, optimal schedules that minimize the maximal tardiness can be constructed using binary search, in
O
(log
n
) iterations of our algorithm. We obtain our results using backward scheduling, a very general relaxation method, which extends, unifies, and clarifies many previous results on instruction scheduling for pipelined and parallel machines.
On the (non-) relationship between SLR(1) and NQLALR(1) grammars
Authors: Bermudez Manuel E. , Schimpf Karl M.
Published: October 2002

A popular but “not-quite” correct technique for computing LALR(1) look-ahead sets has been formalized by DeRemer and Pennello and dubbed NQLALR(l). They also claim that the class of SLR(l) grammars is a subset of the class of NQLALR(1) grammars. We prove here that no such relationship exists between those two classes. We do so with a counterexample that, ironically, appeared in DeRemer and Pennello's own paper.
Determining the extent of lookahead in syntactic error repair
Authors: Mauney Jon , Fischer Charles N.
Published: October 2002

Many syntactic error repair strategies examine several additional symbols of input to guide the choice of a repair; a problem is determining how many symbols to examine. The goal of gathering all relevant information is discussed and shown to be impractical; instead we can gather all information relevant to choosing among a set of “minimal repairs.” We show that finding symbols with the property “Moderate Phrase-Level Uniqueness” is sufficient to establish that all information relevant to these minimal repairs has been seen. Empirical results on the occurrence of such symbols in Pascal are presented.
Transformations of CCP programs
Authors: Etalle Sandro , Gabbrielli Maurizio , Meo Maria Chiara
Published: October 2002

We introduce a transformation system for concurrent constraint programming (CCP). We define suitable applicability conditions for the transformations that guarantee the input/output CCP semantics is also preserved when distinguishing deadlocked computations from successful ones and when considering intermediate results of (possibly) nonterminating computations.The system allows us to optimize CCP programs while preserving their intended meaning: In addition to the usual benefits for sequential declarative languages, the transformation of concurrent programs can also lead to the elimination of communication channels and of synchronization points, to the transformation of nondeterministic computations into deterministic ones, and to the crucial saving of computational space. Furthermore, since the transformation system preserves the deadlock behavior of programs, it can be used for proving deadlock-freeness of a given program with respect to a class of queries. To this aim, it is sometimes sufficient to apply our transformations and to specialize the resulting program with respect to the given queries in such a way that the obtained program is trivially deadlock-free.
Type-preserving compilation of Featherweight Java
Authors: League Christopher , Shao Zhong , Trifonov Valery
Published: October 2002

We present an efficient encoding of core Java constructs in a simple, implementable typed intermediate language. The encoding, after type erasure, has the same operational behavior as a standard implementation using vtables and self-application for method invocation. Classes inherit super-class methods with no overhead. We support mutually recursive classes while preserving separate compilation. Our strategy extends naturally to a significant subset of Java, including interfaces and privacy. The formal translation using Featherweight Java allows comprehensible type-preservation proofs and serves as a starting point for extending the translation to new features. Our work provides a foundation for supporting certifying compilation of Java-like class-based languages in a type-theoretic framework.
Demo-driven design or design-driven demos: vaporware, demos, and prototypes
Authors: Siegel David , Rouchka Tracy
Published: October 2002

Over the years, this column has explored how user-centered design (UCD) fits into the design and development process in the business world. In the context of traditional practices, UCD is often viewed as an added cost, one that has at most long-range benefits. Of course, when a conflict is perceived between what is needed to maximize long-range value and what is needed to successfully meet urgent near-term challenges, the latter usually wins out. Therefore, practitioners of UCD tend to search for examples of how the UCD approach can provide a model for leadership in design and development that integrates the short- and long-term perspectives. This article explores the role that the "demo version" (henceforth referred to simply as the "demo") plays in the product lifecycle, its impact on design, and how UCD can help manage this impact.
Monotone bipartitioning problem in a planar point set with applications to VLSI
Authors: Dasgupta Parthasarathi , Pan Peichen , Nandy Subhas C. , Bhattacharya Bhargab B.
Published: October 2002

A new problem called monotone bipartitioning of a planar point set is identified which is found to be useful in VLSI layout design. Let
F
denote a rectangular floor containing a set
A
of
n
points. The portion of a straight line formed by two points from the set
A
is called a line segment. A
monotone increasing path
(
MP
) in
F
is a connected and ordered sequence of line segments from the bottom-left corner of
F
to its top-right corner, such that the slope of each line segment is nonnegative, and each pair of consecutive line segments share a common point of
A
. An
MP
is said to be maximal (
MMP
) if no other point in
A
can be included in it preserving monotonicity. Let
A

L

denote the subset of
A
corresponding to the end points of the line segments in an
MMP
,
L
. The path
L
partitions the set of points
A
\
A

L

into two subsets lying on its two sides. The objective of monotone bipartitioning is to find an
MMP L
, such that the difference in the number of points in these two subsets is minimum. This problem can be formulated as finding a path between two designated vertices of an edge-weighted digraph (the weight of an edge being an integer lying in the range [-
n, n
]), for which the absolute value of the algebraic sum of weights is minimized. An
O
(
n
×
e
) time algorithm is proposed for this problem, where
e
denotes the number of edges of the graph determined from the geometry of the point set. The monotone bipartitioning problem has various applications to image processing, facility location, and plant layout problems. A related problem arises while partitioning a VLSI floorplan. Given a floorplan with
n
rectangular blocks, the goal is to find a monotone staircase channel from one corner of the floor to its diagonally opposite corner such that the difference in the numbers of blocks lying on its two sides is minimum. The problem is referred to as the staircase bipartitioning problem. The proposed algorithm for a point set can be directly used to solve this problem in
O
(
n
2
) time. However, an improved
O
(
n
) time algorithm is reported for this special case. This leads to an
O
(
n
log
n
) time algorithm for hierarchical decomposition of a floorplan with a sequence of staircase channels. Staircase bipartitioning has many applications to channel and global routing.
Logic transformation for low-power synthesis
Authors: Kim Ki-Wook , Kim Taewhan , Hwang Ting-Ting , Kang Sung-Mo , Liu C. L.
Published: October 2002

In this article we present a new approach to the problem of local logic transformation for reducing power dissipation in logic circuits. The proposed approach overcomes one of the critical limitations common to the previous approaches of local logic transformations for low power, namely, a sequential greedy transformation that identifies signals with high switching activities and then resynthesizes the signals one by one. Instead, we identify a set of signal lines as a group for logic transformation, and determine an order of transformation of the signals with the maximum reduction of power dissipation in the circuit. As a practically feasible solution to this problem, we develop a power model called a finite state input transition (FIT) model, which allows the efficient measurement of the change of power dissipation of the circuit for every possible sequence of logic transformations among the signal lines. Experimental results show that the proposed approach performs an extensive local logic transformation, reducing power consumption by 33% on average without any increase of circuit delay.
Fast placement approaches for FPGAs
Authors: Tessier Russell
Published: October 2002

Recent trends in FPGA development indicate a strong shift toward design reuse through the use of intellectual property (IP). This design shift has motivated the development of Frontier, a timing-driven FPGA placement system that uses design macroblocks in conjunction with a series of placement algorithms to achieve highly routable and high-performance layouts quickly. In the first stage of design placement, a macro-based floorplanner is used to quickly identify an initial layout based on intermacro connectivity. Next, FPGA routability and performance metrics are used to evaluate the quality of the initial placement. Finally, if the floorplan is determined to be insufficient from a routability or performance standpoint, a feedback-driven placement perturbation step is employed to achieve a lower cost placement. For a collection of large reconfigurable computing benchmark circuits our timing-driven placement system exhibits a 2.6× speedup in combined place and route time versus commercial FPGA CAD software with improved design performance for most designs. It is shown that floorplanning, placement evaluation, and backend optimization are all necessary to achieve high-performance placement solutions.
Technology mapping algorithms for domino logic
Authors: Zhao Min , Sapatnekar Sachin S.
Published: October 2002

We present an efficient algorithm for technology mapping of domino logic to a parameterized library. The algorithm is optimal for mapping trees consisting of two-input AND/OR nodes, and has a computation time that is polynomial in terms of constraint size. The mapping method is then extended to DAG covering that permits the implicit duplication of logic nodes. Our synthesis procedure maps the complementary logic cones independently when AND/OR logic is to be implemented, and together using dual-monotonic gates in the case of XOR/XNOR logic. The mapping procedure solves the output phase assignment problem as a preprocessing step. Based on a key observation that the output phase assignment could reduce the implementation cost due to the possible large cost difference between two polarities, a 0--1 integer linear programming formulation was designed to minimize the implementation cost. Our experimental results show the effectiveness of the proposed techniques.
Global array reference allocation
Authors: Araujo Guido , Ottoni Guilherme , Cintra Marcelo Silva
Published: October 2002

Embedded systems executing specialized programs have been increasingly responsible for a large share of the computer systems manufactured every year. This trend has increased the demand for processors that can guarantee high-performance under stringent cost, power, and code size constraints. Indirect addressing is by far the most used addressing mode in programs running on these systems, since it enables the design of small and faster instructions. This paper proposes a solution to the problem of allocating registers to array references using auto-increment addressing modes. It extends previous work in the area by enabling efficient allocation in the presence of control-flow statements. The solution is based on an algorithm that merges address registers' live ranges pairwise. An optimizing DSP compiler, from Mindspeed Technologies Inc., is used to validate this idea. Experimental results reveal a substantial improvement in code performance, when comparing to a combination of local auto-increment detection and priority-based register coloring.
Social networks in the virtual science laboratory
Authors: Chin George , Myers James , Hoyt David
Published: October 2002

Communicating scientists' behavior, as well as their ideas, computer-supported cooperative work technology fosters virtual social networks of far-flung collaborators pursuing mutual interests and experiments.