The performance of two basic external sorting algorithms, distributive sorting and mergesort, is compared in an environment where even the main memory usage involves a cost. Performance is measured by total execution ...
详细信息
The performance of two basic external sorting algorithms, distributive sorting and mergesort, is compared in an environment where even the main memory usage involves a cost. Performance is measured by total execution time and main memory space-time integral. For optimal behavior, both algorithms prefer a small block size and a similar order of external sort. Their memory requirement is similar during the external phase, but during the internal phase distributive sorting requires a larger working space. For small records, the optimal behavior of distributive sorting is obtained with less external passes and its space-time integral is smaller. For large records, the number of passes at the optimal point of mergesort is similar or even less than that of distributive sorting, resulting in a smaller space-time integral. In all cases, the performance of distributive sorting degrades more mildly around the local optima.
Software for controlling hardware dedicated to applications in commercial transaction processing is described. Application programs written initially in a mnemonic language are translated to tables. The system operate...
详细信息
Software for controlling hardware dedicated to applications in commercial transaction processing is described. Application programs written initially in a mnemonic language are translated to tables. The system operates by tasks referring to these application tables being processing by a software processor which either interprets the instructions in the tables directly or issues tasks to other software processors which then perform the required *** software has been implemented on a Raytheon PTS100 mini-computer. A substantial suite of programs has been written for a sales order processing application which involves a network of these machines connected to each other and to a large ICL 1904A computer by telephone links.
We present an optimal algorithm for sorting n integers in the range [1, n(c)] (for any constant c) for the EREW PRAM model where the word length is n(epsilon), for any epsilon > 0. Using this algorithm, the best kn...
详细信息
We present an optimal algorithm for sorting n integers in the range [1, n(c)] (for any constant c) for the EREW PRAM model where the word length is n(epsilon), for any epsilon > 0. Using this algorithm, the best known upper bound for integer sorting on the (O(log n) word length) EREW PRAM model is improved. In addition, a novel parallel range reduction algorithm which results in a near optimal randomized integer sorting algorithm is presented. For the case when the keys are uniformly distributed integers in an arbitrary range, we give an algorithm whose expected running time is optimal.
The paper describes a methodology for the structured description of a distributed program, and its implementation within XMDS, a programming environment for the development of multiprocessor applications. Such program...
详细信息
The paper describes a methodology for the structured description of a distributed program, and its implementation within XMDS, a programming environment for the development of multiprocessor applications. Such programs are composed by a set of concurrent processes, each one consisting of separately compilable modules. The method is compared with those of Ada and Modula-2; the implementation is compared with the approach followed in the design of another programming environment for multimicros.
In 1979, G. K. Manacher showed that the Ford-Johnson sorting algorithm [FJA], acting on t real numbers, can be beaten for an infinite set of values t. These values form a partial cover of constant density not close to...
详细信息
In 1979, G. K. Manacher showed that the Ford-Johnson sorting algorithm [FJA], acting on t real numbers, can be beaten for an infinite set of values t. These values form a partial cover of constant density not close to 1 over an initial sequence of each band running from uk = ⌊(4/3)2k⌋ to uk+l - 1. This early result depended on showing that the Hwang-Lin merging algorithm [HLA], merging m elements with n, m ≠ n, could be surpassed by cm comparisons, where c is an arbitrary small positive *** this paper, it is shown that the FJA can be beaten for a set of integers of asymptotic density 1 under the greatly weakened assumption that the HLA can be surpassed by only (1/2 + ϵ)log m comparisons, with ϵ a small positive constant. The even weaker assumption that no improvement in the HLA exists, but that an isolated value to exists for which the FJA can be surpassed by only (1 + ϵ)log to comparisons yields the same result. Only for a set of “refractory” integers of size about t1/2 in the neighborhood of each uk does the FJA fail to be *** these results depend on a new technique for obtaining optimum sort-merge sequences for best-possible sorting given a merging method. The technique turns out to be amenable to precise asymptotic analysis. When the technique is applied using the most powerful known merging algorithm [Christen's], the density mentioned above is still 1, but islands of refractory points still remain, this time forming sets provably of size Θ(log2t) in the neighborhood of each *** is shown that if “information theoretic” merging were achievable, the FJA could be beaten for all t > u10 = 1365. From these results and a few others, we adduce evidence in support of our main conjecture: that even optimum combinations of optimum merging and Ford-Johnson sorting will not beat the FJA when t = uk, but will instead produce refractory regions of size Θ(log2t) in the neighborhood of each λ.
A new measure of presortedness is presented which we call Par . We prove that it is distinct from other common measures of presortedness and we design sorting algorithms that sort a sequence X in O (| X | log Par ( X ...
详细信息
A new measure of presortedness is presented which we call Par . We prove that it is distinct from other common measures of presortedness and we design sorting algorithms that sort a sequence X in O (| X | log Par ( X )) comparisons. Moreover, we prove that this is Par -optimal in a comparison-based model of computation.
Few would disagree with the assertion that safe engineering starts from the early stages of system design and should be maintained throughout the lifecycle. Different engineering domains have developed, mostly informa...
详细信息
Few would disagree with the assertion that safe engineering starts from the early stages of system design and should be maintained throughout the lifecycle. Different engineering domains have developed, mostly informal, frameworks with which they hope to promote this attitude. An interesting question for the KBS community is whether some of our methods for knowledge representation and reasoning can be used to assist in understanding, representing and interpreting such frameworks. This paper concentrates on what is (arguably) the area of greatest concern: relating system requirements to high level design. We highlight what appear to be the major difficulties which face us in this area, using examples from systems which have been built to tackle them.
A model of a multiprocessing, multiprogrammingcomputer system with serially reusable programs was developed to study the effect of serial programs on system performance. Two strategies for implementing serially reusa...
详细信息
A model of a multiprocessing, multiprogrammingcomputer system with serially reusable programs was developed to study the effect of serial programs on system performance. Two strategies for implementing serially reusable programs were investigated, a wait strategy in which the processor waits until the serial program is available, and a switch strategy, in which the processor is freed to do other work. Relative performances and asymptotic conditions as functions of the number of processors, processes, serially reusable programs, and the fraction of time each process executes serially reusable programs were obtained. Quantitative results are presented showing that the switch strategy is superior. The wait strategy causes quick saturation when the number of processes is increased.
This paper describes an empirical comparison of the effectiveness of six context-insensitive pointer analysis algorithms that use varying degrees of flow-sensitivity. Four of the algorithms are flow-insensitive, one i...
详细信息
This paper describes an empirical comparison of the effectiveness of six context-insensitive pointer analysis algorithms that use varying degrees of flow-sensitivity. Four of the algorithms are flow-insensitive, one is flow-sensitive, and another is flow-insensitive, but uses precomputed flow-sensitive information. The effectiveness of each analysis is quantified in terms of compile-time efficiency and precision. Efficiency is reported by measuring CPU time and memory consumption of each analysis. Precision is reported by measuring the computed solutions at the program points where a pointer is dereferenced. The results of this paper will help implementors determine which pointer analysis is appropriate for their application. (C) 2001 Elsevier Science B.V. All rights reserved.
The problem of merging two large ordered sets A and B is considered. A detailed description of the development of an efficient parallel algorithm is given, starting with a version of the algorithm that demonstrates th...
详细信息
The problem of merging two large ordered sets A and B is considered. A detailed description of the development of an efficient parallel algorithm is given, starting with a version of the algorithm that demonstrates the idea of partitioning the merge problem into independent subproblems and ending with an optimal parallel algorithm for the EREW P- RAM model of computation.
暂无评论