Optimal program slicing determines for a statement S in a program π whether or not S affects a specified set of statements, given that all conditionals in π are interpreted as non-deterministic choices. Only recentl...
详细信息
ISBN:
(纸本)9781581133493
Optimal program slicing determines for a statement S in a program π whether or not S affects a specified set of statements, given that all conditionals in π are interpreted as non-deterministic choices. Only recently, it has been shown that reachability of program points and hence also optimal slicing is undecidable for multi-threaded programs with (parameterless) procedures and synchronization. Here, we sharpen this result by proving that slicing remains undecidable if synchronization is abandoned - although reachabitity becomes polynomial. Moreover, we show for multithreaded programs without synchronization, that slicing stays PSPACE-hard when procedure calls are forbidden, and becomes NP-hard for loop-free programs. Since the latter two problems can be solved in PSPACE and NP, respectively, even in presence of synchronization, our new lower bounds are tight. Finally, we show that the above decidability and lower bound properties equally apply to other simple program analysis problems like copy c onstant propagation and true liveness of variables. This should be contrasted to the problems of strong copy constant propagation and (ordinary) liveness of variables for which polynomial algorithms have been designed.
Retrograde analysis is an efficient exhaustive search method. It is a powerful tool that can be used in solving problems where end states have known values but starting states do not. It has been widely used to solve ...
详细信息
ISBN:
(纸本)0769512968
Retrograde analysis is an efficient exhaustive search method. It is a powerful tool that can be used in solving problems where end states have known values but starting states do not. It has been widely used to solve mathematically-precise games such as chess endgames, and is potentially usable in energy-minimization problems. With increasing computing power, both in speed and storage capacity, retrograde analysis will become more and more useful. This paper looks at successful applications to games, the challenges ahead, and the modifications that are required to utilize distributed hardware. The power and the usefulness of retrograde analysis are still limited by the computing resources one has access to. Today, the best sequential retrograde algorithms are capable of solving problems with about 109 states in a few hours on a standard personal computer Bigger problems need more powerful computers, or take much longer to solve, or are simply out of reach of today's technologies, Introducing parallelism to retrograde analysis is a natural way to attack the bigger problems. There are today three main architectures available for doing parallel retrograde analysis: namely Symmetric Multiprocessor systems, High-speed network based distributed systems, and Internet based distributed systems. In this paper, we discuss some of the key issues in doing parallel retrograde analysis on these different architectures. Technical challenges are addressed in detail, as well as some examples and proposals. These examples and proposals are drawn from various board games, but the ideas can be applied to other problem domains.
We address the problem of prefetching and caching in a parallel I/O system and present a new algorithm for optimal parallel-disk scheduling. Traditional buffer management algorithms that minimize the number of I/O dis...
ISBN:
(纸本)9781581134094
We address the problem of prefetching and caching in a parallel I/O system and present a new algorithm for optimal parallel-disk scheduling. Traditional buffer management algorithms that minimize the number of I/O disk accesses, are substantially suboptimal in a parallel I/O system where multiple I/Os can proceed *** present a new algorithm SUPERVISOR for parallel-disk I/O scheduling. We show that in the off-line case, where apriori knowledge of all the requests is available, SUPERVISOR performs the minimum number of I/Os to service the given I/O requests. This is the first parallel I/O scheduling algorithm that is provably offline optimal. In the on-line case, we study SUPERVISOR in the context of global L-block lookahead, which gives the buffer management algorithm a lookahead consisting of L distinct requests. We show that the competitive ratio of SUPERVISOR, with global L-block lookahead, is Θ(M - L + D), when L ≤ M, and Θ(MD/L), when L > M, where the number of disks is D and buffer size is M.
We consider parallel machine scheduling problems where the jobs are subject to precedence constraints, and the processing times of jobs are governed by independent probability distributions. The objective is to minimi...
ISBN:
(纸本)9780898714906
We consider parallel machine scheduling problems where the jobs are subject to precedence constraints, and the processing times of jobs are governed by independent probability distributions. The objective is to minimize the weighted sum of job completion times ∑, w, C, in expectation, where w, ⪈ 0. Building upon an LP-relaxation from [3] and an idle time charging scheme from [1], we derive the first approximation algorithms for this model.
Gas Chromatographs are extensively used in the lab for analysis of collected samples and in the field for continuous analysis of Natural Gas to determine the energy content and relative density of Natural Gas. Gas chr...
详细信息
Gas Chromatographs are extensively used in the lab for analysis of collected samples and in the field for continuous analysis of Natural Gas to determine the energy content and relative density of Natural Gas. Gas chromatographs (GC) are not typically used for analysis of other gas quality properties. There are several new applications utilizing recent developments in parallel Chromatography that expand the use of GCs in Natural Gas Quality Measurements. Three new applications are: C9+ Measurement for hydrocarbon Dewpoint calculations Measurement of energy content with analysis to C6+ including measurement of trace levels of Hydrogen Sulfide (H2S) in the 0-30 ppm range. Measurement of energy content with analysis to C6+ including measurement of trace levels of Helium (He) and Hydrogen (H2) in Natural Gas. These additional analytical measurements are typically performed with auxiliary analyzers. Although some of these advanced GC applications have been done in the lab, the use of complex detectors for Chromatographic analysis was necessary. Flame Photometric Detectors (FPD) or Flame Ionization Detectors (FID) were typically used rather than a simple Thermal Conductivity Detector (TCD). This limited the use of GCs for continuous measurement of other gas quality properties in field installations. This paper will discuss recent advancements in parallel chromatography that allow the use of basic TCDs in GC applications for gas quality analysis in the field. This increased GC capability and simplified detection method reduces the equipment cost and maintenance cost associated with total gas quality analysis at meter stations.
We consider the problem of scheduling unit-length jobs on identical parallel machines such that the makespan of the resulting schedule is minimized. Precedence constraints impose a partial order on the jobs, and both ...
ISBN:
(纸本)9780898714906
We consider the problem of scheduling unit-length jobs on identical parallel machines such that the makespan of the resulting schedule is minimized. Precedence constraints impose a partial order on the jobs, and both communication and precedence delays impose relative timing constraints on dependent jobs. The combination of these two types of timing constraints naturally models the instruction scheduling problem that occurs during software compilation for state-of-the-art VLIW (Very Long Instruction Word) processors and multiprocessor parallel *** present the first known polynomial-time algorithm for the case where the precedence constraint graph is a forest of in-trees (or a forest of out-trees), the number of machines m is fixed, and the delays (which are a function of both the job pair and the machines on which they run) are bounded by a constant *** algorithm relies on a new structural theorem for scheduling jobs with arbitrary precedence constraints. Given an instance with many independent dags, the theorem shows how to convert, in linear time, a schedule S for only the largest dags into a complete schedule that is either optimal or has the same makespan as S.
For the design and analysis of algorithms that process huge data sets, a machine model is needed that handles parallel disks. There seems to be a dilemma between simple and flexible use of such a model and accurate mo...
ISBN:
(纸本)9780898714906
For the design and analysis of algorithms that process huge data sets, a machine model is needed that handles parallel disks. There seems to be a dilemma between simple and flexible use of such a model and accurate modelling of details of the hardware. This paper explains how many aspects of this problem can be resolved. The programming model implements one large logical disk allowing concurrent access to arbitrary sets of variable size blocks. This model can be implemented efficienctly on multiple independent disks even if zones with different speed, communication bottlenecks and failed disks are allowed. These results not only provide useful algorithmic tools but also imply a theoretical justification for studying external memory algorithms using simple abstract *** algorithmic approach is random redundant placement of data and optimal scheduling of accesses. The analysis generalizes a previous analysis for simple abstract external memory models in several ways (Higher efficiency, variable block sizes, more detailed disk model). As a side effect, an apparently new Chernoff bound for sums of weighted 0-1 random variables is derived.
The papers submitted to the Tenth annual acm symposium on parallel algorithms and architectures are presented. The issues considered include network protocols, parallelalgorithms, multiprocessing systems, parallel pr...
详细信息
The papers submitted to the Tenth annual acm symposium on parallel algorithms and architectures are presented. The issues considered include network protocols, parallelalgorithms, multiprocessing systems, parallel processing systems, distributed computer systems, program compilers, sorting, computer science, data storage equipment, video signal processing.
To obtain the benefits of aggressive, wide-issue, architectures, a large window of valid instructions must be available. While researchers have been successful in obtaining high accuracies with a range of dynamic bran...
详细信息
ISBN:
(纸本)0780373154
To obtain the benefits of aggressive, wide-issue, architectures, a large window of valid instructions must be available. While researchers have been successful in obtaining high accuracies with a range of dynamic branch predictors, there still remains the need for more aggressive instruction delivery. Loop bodies possess a large amount of spatial and temporal locality. A large percentage of a program's entire execution can be attributed to code found in loop bodies. If we retain this code in a buffer or the cache, we do not have to refetch this code on subsequent loop iterations., Loops tend to iterate multiple times before exiting, thus providing us with the opportunity to speculatively issue multiple iterations. While some loops can be unrolled by a compiler many contain conditional branches. The number of times a loop iterates may be dependent on a program variable. These issues can hinder our ability to speculatively issue multiple iterations of a loop. If we are able to profile loops during runtime, we can use this information to more accurately issue speculative paths through loop bodies. In this paper we present a characterization of loop execution across the SPECint2000 benchmark suite. We intend for this study to serve as a guide in the selection of design parameters of a loop path predictor We characterize the patterns exhibited during multiple visits to a loop body. We present the design of a table that records path-based loop execution history and allows us to predict multiple loop iterations dynamically.
暂无评论