From jpe@ida.liu.se Fri May 27 13:36:06 1994 From: Jan Petersson Date: Sat, 21 May 94 17:59:06 +0200 To: challenge3@dimacs.rutgers.edu Subject: progress report Cc: janpe@ida.liu.se \documentstyle[11pt]{article} \textwidth = 150mm \textheight = 240mm \unitlength = 1mm \topmargin = -5mm \pagestyle{plain} \begin{document} \title{The Third DIMACS International\\ Algorithm Implementation Challenge\\[5mm] Progress Report:\\ SIMD-MCC Algorithms for Geometric\\ Dominance and Proximity Problems} \author{Jan Petersson\\ Department of Computer and Information Science\\ Link\"{o}ping University, S--581\,83 Link\"{o}ping, Sweden\\ email: \mbox{\tt janpe@ida.liu.se} } \date{} \maketitle %===================================================================== This progress report is divided into a {\bf revised proposal}, influenced by the comments received (thanks!) and by experiences gained the past few months, and a {\bf status report}, describing what has been achieved so far. %===================================================================== \section*{Revised proposal} We still intend to study algorithms for the geometric dominance and proximity problems listed in our original proposal. %--------------------------------------- %{\sc Dominance Counting}. %{\sc Maxima}. %{\sc Closest Pair.} %{\sc All Nearest Neighbors.} %{\sc Euclidean Minimum Spanning Tree}. %--------------------------------------- But we will be less concerned with solutions available in the literature. Rather we will develop ``new'' algorithms for these problems, because this often seems to be easier when it comes to implementation (and perhaps detailed analysis). We are primarily interested in algorithms based on the divide-and-conquer technique. It is our ambition to develop algorithms that are efficient not only in the usual asymptotic sense,\linebreak but also exhibit good (worst-case) performance for realistic input sizes. \medskip For experimental evaluation, we will use the MasPar MP--1 computer. For coding purposes, we will use the MPL language. To enable comparisons with theoretical results, we will use only the features of MPL/MP--1 that comply with our model of computation. Thus, it is not our ambition to develop fast algorithms for this particular computer. (Besides, it has turned out that most built-in routines are less suitable for the kind of algorithms we have in mind.) Our primary measure of performance will be elapsed time. Comparison with efficient workstation implementations of (the corresponding) sequential algorithms will be included (as~suggested). \medskip A preliminary agenda is given below. Since time certainly will be a crucial factor here (this is basically a one-man project), we are a bit anxious to know whether the current delay will be propagated throughout the implementation challenge, or are extended abstracts still due to August 15. Also, further comments would be appreciated. \newpage \subsubsection*{Dominance problems} %--------------------------------------- \begin{enumerate} \item %******* Develop divide-and-conquer algorithms for the planar case. \item %******* Develop divide-and-conquer algorithms for the multidimensional case. \item %******* Implement and evaluate algorithms for the case of ``bounded'' input sizes,\\ i.e. sizes no larger than the number of physical processors (16\,384). \item %******* Study virtualization techniques for the above algorithms. \item %******* Implement and evaluate algorithms for the case of ``unbounded'' input sizes,\\ i.e. sizes limited only by the memory available (about a million input points.) \end{enumerate} %--------------------------------------- \subsubsection*{Proximity problems} %--------------------------------------- \begin{enumerate} \setcounter{enumi}{5} \item %******* Develop ``region approach'' algorithm the planar All Nearest Neighbors. \\[\parsep] A solution based on this approach has been proposed for the PRAM model.\\ Our algorithm for planar Dominance Counting can be used here \ldots \item %******* Develop (direct) divide-and-conquer algorithm the planar All Nearest Neighbors. \item %******* Implement and evaluate. \item %******* Develop algorithm for the planar (Euclidean) Minimum Spanning Tree. \\[\parsep] Currently, we have no idea of our own for this problem. Therefore, we will probably elaborate on the solution outlined by Miller \& Stout. \item %******* Implement and evaluate. \end{enumerate} %--------------------------------------- \subsubsection*{If time permits \ldots} %--------------------------------------- \begin{itemize} \item %******* Implement and evaluate some algorithms from the literature, for example: \begin{itemize} \item Dehne's algorithm for Dominance Counting. \item Miller \& Stout's algorithm for All Nearest Neighbors. \end{itemize} \item %******* Study proximity problems in higher dimensions. \begin{itemize} \small \item the multidimensional Closest Pair problem. \item the 3-dimensional All Nearest Neighbors and Minimum Spanning Tree problems. \normalsize \end{itemize} \item %******* Study compression techniques for some divide-and-conquer algorithms. \\[\parsep] For the Maxima and Closest Pair problems, input points can successively be removed from further consideration. How can this be exploited in our model of computation? \item %******* Study other algorithm design techniques, for example, cell-based methods. \\[\parsep] This kind of algorithms are often fast in practice (i.e. for most point distributions). \item %******* Study problem variants, for example: \begin{itemize} \item semi-dynamic problems (as suggested). \item batched query problems (i.e. queries are known in advance). \end{itemize} \end{itemize} %--------------------------------------- \subsubsection*{Further remarks} In the comments received, it was suggested that we should not restrict attention to uniform point distributions. We will certainly follow this advise, but for the algorithms developed so far the distribution is actually not crucial. When this is the case, we will consider some non-uniform distributions from: \begin{quote} J.L. Bentley. $k$-d trees for semi-dynamic point sets. In {\em Proc. 6th Annual ACM Symposium on Computational Geometry\/}, pages 187--197, 1990. \end{quote} We will also use the input instances referred to in the comments. %===================================================================== \section*{Status Report} The first three items on our list has been completed. That is, we have developed and implemented $O(d\,(2 + \sqrt{2})^{\,d} \sqrt{n})$ algorithms for dominance problems in $d$-dimensional space. %($d \geq 2)$. Our solutions are based on the multidimensional divide-and-conquer technique, and use a recursive decomposition of the mesh obtained by indexing in shuffled row major order. Since this indexing scheme is not supported by the system (and for reasons stated above), we have also implemented various fundamental data movement operations, including the bitonic sort algorithms of Thompson \& Kung and Nassimi \& Sahni. \medskip We have also conducted some experiments (item~3). In the planar case, for example, about 350~milliseconds (Dominance Counting) and 250~milliseconds (Maxima) is required to solve a problem of size 16\,384. To help judge our implementations, and hence to get a more clear picture of what might be obtained on the MP--1 computer, we have examined in greater detail communication costs per se: at most 20\,\% of the total time is spent here. (In this way, we can perhaps be less concerned with implementation details?) \medskip The corresponding sequential algorithms have been coded in the C language, and executed on a SUN SLC workstation. For the above input size, the parallel algorithms turned out to be about 20~times faster in the planar case. Moreover, this ``speedup'' growths with increasing dimension. (To make this kind of comparisons more ``fair'', we should perhaps consider a more powerful workstation?) \medskip Finally, we are currently working with virtualization (item~4 and~5). As we move to proximity problems, we will contact the participants in the ``Parallel Nearest Neighbors'' project, Talmor \& Narlikar. %===================================================================== \end{document}