Parallelizing divide-and-conquer algorithms — Microtasking versus autotasking

Autor:	Renate Knecht
Rok vydání:	1990
Předmět:	Convex hull Divide and conquer algorithms LOOP (programming language) Computer science business.industry Fortran Parallel algorithm Parallel computing Fragment (logic) Human multitasking business computer Subdivision computer.programming_language
Zdroj:	CONPAR 90 — VAPP IV ISBN: 9783540530657 CONPAR
DOI:	10.1007/3-540-53065-7_132
Popis:	Algorithms based on a divide-and-conquer strategy are well qualified for being implemented in a multitasking environment. The idea of the divide-and-conquer paradigm is to fragment a problem into subproblems of the same kind, to solve the subproblems recursively, and, finally, to combine the solutions of the subproblems into a solution of the original problem. The subdivision in smaller problems which can be solved independently provides the possibility for parallel execution on multiple processors. In this paper the parallel implementation of a divide-and-conquer algorithm to compute the convex hull in the plane is discussed. The algorithm is implemented in FORTRAN on a CRAY Y-MP8/832 using the CRAY multitasking strategies. The concepts of microtasking and autotasking are compared with respect to their qualification for the parallelization of REPEAT loop constructs which constitute the main part of the described divide-and-conquer algorithm.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::8fc73e1b8651a4d757cfc4b7f669482c https://doi.org/10.1007/3-540-53065-7_132 Zobrazit plný text záznamu