Author name cluster

T. Hagerup

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

I&C Journal 1995 Journal Article

A Lower-Bound for the Emulation of PRAM Memories on Processor Networks

T. Hagerup

We show a lower bound of Ω(min{log m, √n}) on the slowdown of any deterministic emulation of a PRAM memory with m cells and n I/O ports on an n-processor bounded-degree network. The bound is weak; unlike all previous bounds, however, it does not depend on the unnatural assumption of point-to-point communication which says, roughly, that messages in transit cannot be duplicated by intermediate processors. For m sufficiently large relative to n, the new bound implies the optimality of a simple emulation on a mesh-of-trees network.

Details DOI

I&C Journal 1995 Journal Article

Fast Parallel Space Allocation, Estimation, and Integer Sorting

H. Bast
T. Hagerup

The following problems are shown to be solvable in O(log* n) time with optimal speedup with high probability on a randomized CRCW PRAM using O(n) space: • Space allocation: Given nonnegative integers, .. ., , allocate nonoverlapping blocks of consecutive memory cells of sizes, .. ., from a base segment of (∑) consecutive memory cells. • Estimation: Given integers in the range 1. ., compute "good" estimates of the number of occurrences of each value in the range 1. .. • Semisorting: Given integers, .. ., in the range 1. ., store the integers 1, .. ., in an array of () cells such that for all ∈ {1, .. ., }, all elements of {: 1 ≤ ≤ and = } occur together, separated only by empty cells. • Integer chain-sorting: Given integers, .. ., in the range 1. ., construct a linked list containing the integers 1, .. ., such that for all, ∈ {1, .. ., }, if precedes in the list, then ≤. Moreover, given slightly superlinear processor and space bounds, these problems or variations of them can be solved in constant time with high probability. As a corollary of the integer chain-sorting result, it follows that n integers in the range 1. .n can be sorted in O(log n/log log n) time with optimal speedup with high probability.

Details DOI

I&C Journal 1991 Journal Article

Improved deterministic parallel integer sorting

P.C.P. Bhatt
K. Diks
T. Hagerup
V.C. Prasad
T. Radzik
S. Saxena

We consider the problem of deterministic sorting of integers on a parallel RAM (PRAM). The best previous result (T. Hagerup, 1987, Inform. and Comput. 75, 39–51) states that n integers of size polynomial in n can be sorted in time O(log n) on a Priority CRCW PRAM with O( n log log n log n ) processors. We prove that n integers drawn from a set {0, …, m−1} can be sorted on an Arbitrary CRCW PRAM in time O( log n log log n + log log m) with a time-processor product of O(n log log m). In particular, if m = n (log n) O(1), the time and number of processors used are O( log n log log n ) and O( n(log log n)2 log n ), respectively. This improves the previous result in several respects: The new algorithm is faster, it works on a weaker PRAM model, and it is closer to optimality for input numbers of superpolynomial size. If log log m = O( log n log log n ), the new algorithm is optimally fast, for any polynomial number of processors, and if log log m = (1 + Ω(1)) log log n and log log m = 0( log n ), it has optimal speedup relative to the fastest known sequential algorithm. The space needed is O(nm ε ), for arbitrary but fixed ε > 0. The sorting algorithm derives its speed from a fast solution to a special list ranking problem of possible independent interest, the monotonic list ranking problem. In monotonic list ranking, each list element has an associated key, and the keys are known to increase monotonically along the list. We show that monotonic list ranking problems of size n can be solved optimally in time O( log n log log n ). We also discuss and attempt to solve some of the problems arising in the precise description and implementation of parallel recursive algorithms. As part of this effort, we introduce a new PRAM variant, the allocated PRAM.

Details DOI