The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
In this paper we design and analyse parallel algorithms with the goal to get exact bounds on their speed-ups on real machines. For this purpose we define an extension of Valiant's BSP model, BSP*, that rewards blockwise communication, and uses Valiant's notion of c-optimality. Intuitively a c-optimal parallel algorithm for p processors achieves speed-up close to p/c. We consider the Multisearch problem:...
In this paper, we explore parallel implementations of the abstract data type priority queue. We use the BSP* model, an extension of Valiant's BSP model which rewards blockwise communication, i.e. sending a few large messages instead of many small ones. We present two randomized approaches for different relations between the size of the data structure and the number of parallel updates to be performed...
Searching is one of the most important algorithmic problems, used as a subroutine in many applications. Accordingly, designing search algorithms is in the center of research on data structures since decades. In this paper we aim to survey recent developments in designing parallel search algorithms where parallel machines are used to answer many search queries in parallel, so called multisearch algorithms...
Given m ordered segments that form a partition of some universe (e.g., a 2D strip), the multisearch problem consists of determining, for a set of n query points in the universe, the segments they belong to. We present the first parallel deterministic scheme that efficiently solves the problem in the case m ≥ n. The scheme is designed on the BSP model, a variant of Valiant's BSP that rewards blockwise...
In this paper we design and analyse parallel algorithms with the goal to get exact bounds on their speed-ups on real machines. For this purpose we define an extension of Valiant's BSP model, BSP * , that rewards blockwise communication, and use Valiant's notion of 1-optimality. Intuitively, a 1-optimal parallel algorithm for p processors achieves speed-up close to p. We consider the Multisearch...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.