When writing a Basic program that involves sorting of names or numbers, selection of the sorting method can be important to program speed. It is shown how sorting methods work, so informed selections of when and why o...
详细信息
When writing a Basic program that involves sorting of names or numbers, selection of the sorting method can be important to program speed. It is shown how sorting methods work, so informed selections of when and why one method should be chosen over another can be made. Some good textbooks are recommended to learn about sorting algorithms. A program is introduced to permit clearly the visualization of three common sorting methods on the screen. It dramatically shortens the time needed to understand why one method beats another. In operation, it builds a disordered array of ASCII characters, displays it and then proceeds to illustrate a step-by-step sort by the methods known as bubble sort, quicksort, and fastsort. As it goes, it displays a report on how many comparisons and swaps were necessary to achieve order.
Consideration of two pairs of producer-consumer sharing a finite buffer. In order not to let any pair block the other, the buffer is partitioned. Each time a message enters the buffer, the system gets a reward. Under ...
详细信息
Consideration of two pairs of producer-consumer sharing a finite buffer. In order not to let any pair block the other, the buffer is partitioned. Each time a message enters the buffer, the system gets a reward. Under Markovian assumptions for both production and consumption processes, the author determines the partition that maximize the long term average reward per unit of time. The optimal solution and a measure of its efficiency are analyzed.
In this paper, a new method of evaluation for information system project is proposed on the basis of the meta-synthesis methodology from qualitative analysis to quantitative analysis. DHGF is an integrated method of i...
详细信息
In this paper, a new method of evaluation for information system project is proposed on the basis of the meta-synthesis methodology from qualitative analysis to quantitative analysis. DHGF is an integrated method of improved Delphi, analytic hierarchy process, grey interconnect degree and fuzzy comprehensive evaluating. It gives full play to their advantages and controls theirs disadvantages. The feasibility and effectiveness of DHGF are shown in the practical example.
Self-applicable partial evaluation has been implemented for half a decade now, but many problems remain open. This paper addresses and solves the problems of automating call unfolding, having an open-ended set of oper...
详细信息
Self-applicable partial evaluation has been implemented for half a decade now, but many problems remain open. This paper addresses and solves the problems of automating call unfolding, having an open-ended set of operators, and processing global variables updated by side effects. The problems of computation duplication and termination of residual programs are addressed and solved: residual programs never duplicate computations of the source program;residual programs do not terminate more often than source programs. This paper describes the automatic autoprojector (self-applicable partial evaluator) Similix;it handles programs with user-defined primitive abstract data type operators which may process global variables. Abstract data types make it possible to hide actual representations of data and prevent specializing operators over these representations. The formally sound treatment of global variables makes Similix fit well in an applicative order programming environment. We present a new method for automatic call unfolding which is simpler, faster, and sometimes more effective than existing methods: it requires neither recursion analysis of the source program, nor call graph analysis of the residual program. To avoid duplicating computations and preserve termination properties, we introduce an abstract interpretation of the source program, abstract occurrence counting analysis, which is performed during preprocessing. We express it formally and simplify it.
Due to advances in integrated circuit technology, multiprocessor systems with more than two Central Processing Units are becoming economically feasible. For this reason, the study of such systems with the aim of devel...
详细信息
Due to advances in integrated circuit technology, multiprocessor systems with more than two Central Processing Units are becoming economically feasible. For this reason, the study of such systems with the aim of developing more efficient hardware and software structures is gaining interest. One type of multiprocessor structure which has recently received some attention is the dynamically microprogrammable multiprocessor system. This paper investigates the problems of efficiently allocating the processors of such a system among the system's workload.A collection of algorithms and scheduling procedures is developed which may be used for processor allocation in dynamically microprogrammable multiprocessor systems with an arbitrary number of processors. Proofs that these algorithms produce configurations which optimise certain measures are given. The algorithms are practical in the sense that the computation required increases linearly with respect to the number of processors to be allocated. Finally, a simulation study has shown that in many circumstances the use of these algorithms can be expected to yield a significant improvement in system performance over an allocation scheme previously proposed.
An approach to efficiently customizing programs is developed here. A Pascal-like language has been developed for which the transformational semantics of ordinary and mixed computations have been constructed. The attai...
详细信息
An approach to efficiently customizing programs is developed here. A Pascal-like language has been developed for which the transformational semantics of ordinary and mixed computations have been constructed. The attainment of a system is described through which parsers were obtained for several existing programming languages. The results of a machine experiment are presented.
We present a simple and uniform transformational system for extracting parallelism from programs. The transformations are studied as a formal system. We define a measure of program improvement, and show that the trans...
详细信息
We present a simple and uniform transformational system for extracting parallelism from programs. The transformations are studied as a formal system. We define a measure of program improvement, and show that the transformations improve programs with respect to the measure. We show that it is possible to compute limits of infinite sequences of the transformations; this allows our system to implement software pipelining, and leads to a general solution to the problem of software pipelining in the presence of tests. Using the primitive transformations and the limit-taking transformation, it is possible to express the classical parallelization techniques for vector, multiprocessor, and VLIW machines. Thus, our transformational system can be viewed as a formal foundation for the area of parallelization. We present implementations of two techniques, doacross and a simple form of vectorization.
A multiprocessing system composed of identical units is considered. This system is executing a set of partially ordered tasks, with known execution times, using a non-preemptive scheduling strategy. Lower bounds on th...
详细信息
A multiprocessing system composed of identical units is considered. This system is executing a set of partially ordered tasks, with known execution times, using a non-preemptive scheduling strategy. Lower bounds on the number of processors required to compute the tasks before a deadline, and on the minimum time to execute the tasks with a fixed number of processors, are of great value for the determination of the corresponding optimal schedules. In this paper, methods for the efficient computation of the lower bounds obtained by Fernndez and Bussell are discussed. Computational improvements for the case of general partial orders are reported, and further reductions of the number of operations are shown to be possible for special graphs (trees, independent chains, independent tasks).
We present a cost-optimal parallel algorithm for traversing a general tree in breadth-first fashion. For a tree with n nodes, this algorithm requires O(n/p + log n) time employing p processors on the EREW PRAM model. ...
详细信息
We present a cost-optimal parallel algorithm for traversing a general tree in breadth-first fashion. For a tree with n nodes, this algorithm requires O(n/p + log n) time employing p processors on the EREW PRAM model. To the best of our knowledge, it is the first parallel algorithm for breadth-first tree-traversal, which has O(log n) time complexity and yet being cost-optimal for p = O(n/log n) on the EREW PRAM. Our approach is based on a novel idea which converts the breadth-first traversal problem into a parentheses matching problem. As an application of this technique, we design a simple but elegant parallel algorithm for sorting a special class of integers in which elements in any two consecutive places of the input sequence differ at most by unity. The proposed sorting algorithm is stable and it achieves the same performance as that of our breadth-first traversal algorithm.
This paper describes a novel application of algebraic specification techniques and a combination of human and mechanical theorem proving to prove 'correctness' for a simple verification condition generator (VC...
详细信息
This paper describes a novel application of algebraic specification techniques and a combination of human and mechanical theorem proving to prove 'correctness' for a simple verification condition generator (VCG) - part of a program verifier. A two-step process is employed to show consistency between the VCG implementation and the primary specification.
暂无评论