Fringe analysis for parallel MacroSplit insertion algorithms in 2--3 trees
Abstract
We extend the fringe analysis (used to study the expected behavior of balanced search trees under sequential insertions) to deal with synchronous parallel insertions on 2--3 trees. Given an insertion of k keys in a tree with n nodes, the fringe evolves following a transition matrix whose coefficients take care of the precise form of the algorithm but does not depend on k or n. The derivation of this matrix uses the binomial transform recently developed by P. Poblete, J. Munro and Th. Papadakis. Due to the complexity of the preceding exact analysis, we develop also two approximations. A first one based on a simplified parallel model, and a second one based on the sequential model. These two approximated analysis prove that the parallel insertions case does not differ significantly from the sequential case, namely on the terms O(1/n^2).
Full text
Fringe analysis for parallel MacroSplit insertion algorithms in 2{3 trees ? (extended abstract) R. Baeza-Yates 1 , J. Gabarro 2 , and X. Messeguer 2 1 Departamento de Ciencias de la Computacion, Universidad de Chile, Blanco Encalada 2120, Santiago, Chile. E-mail: [email protected]hile.cl 2 LSI, Universitat Politecnica de Catalunya, Modul C5-C6, C/ Jordi Girona, 1-3, E-Barcelona 08034, Spain. E-mail: f gabarro , p eyp o ch g @lsi.up c.es Abstract. We extend the fringe analysis (used to study the exp ected b ehavior of balanced search trees under sequential insertions) to deal with synchronous parallel insertions on 2{3 trees. Given an insertion of k keys in a tree with n no des, the fringe evolves following the transition matrix: T nk = 1+ k n +1 I + k X j =0 ( ; 1) j ( n +1) j k j ! j ; j ; j j : where the co ecients j and j take care of the precise form of the algorithm but do es not dep end on k or n . The derivation of this matrix uses the binomial transform recently develop ed byP.Poblete, J. Munro and Th. Papadakis. Due to the complexity of the preceding exact analysis, we develop also two approximations . A rst one based on a simplied parallel mo del, and a second one based on the sequential mo del. These two approximated analysis prove that the parallel insertions case do es not dier signicantl y from the sequential case, namely on the terms O (1 =n 2 ). Keywords: Fringe analysis, Parallel algorithms, 2-3 trees, Binomial transform. 1 Intro duction One of the basic problems of managing information is the dictionary problem, where a set of keys has to b e dynamically maintained. One solution to this problem are balanced search trees. One example are 2{3 trees where all leaves app ear at the same depth and every no de has either one key and twosons, or twokeys and three sons. The exact analysis of the sequential case is still ? Partially supp orted byACI-CONICYT through Catalunya-Chile Co op eration Program (DOG 2320-30.1.1997) and RITOS network (CYTED) and ESPRIT Long Term Research Pro ject no. 20244{ALCOM IT and DGICYT under grant PB95-0787 (pro ject KOALA) and CICIT TIC97-1475-CE.
op en, but go o d lower and upp er b ounds for several complexity measures have b een obtained Yao78,EZG + 82,BYP95] using a technique called fringe analysis BY95]. This analysis studies the b ottom subtrees or fringe of trees and has b een applied to most search trees. We use this technique to analyze k synchronous parallel insertions in 2-3 trees for k> 0. The rest of the pap er is organized as follows. In section 2 weintro duce the MacroSplit based synchronous parallel insertion algorithm, which is at the base of our fringe approach. In section 3, some qualitative explanations ab out existing insertions algorithms are given. Section 4 develops the fringe analysis giving an exact result for the transition matrix (theorem 2). The complexity of the results has forced us to address two approximations in section 5. In the rst we add some assumptions to the parallel algorithm, and in the second we consider consecutive sequential insertions. Section 6 we include nal remarks and future works. Finally, in the app endix we give a complete pro of, using the binomial transform PMP95], of the theorem 2. 2 MacroSplit based parallel insertion algorithm Weintro duce a parallel insertion algorithm based on the idea of MacroSplit .On this algorithm an array of ordered keys a 1 :: ] is inserted into a 2-3 tree having n leaves. The MacroSplit insertions algorithm has two main successive phases. Percolation Phase. In a top-down strategy, the set of keys to b e inserted is split into several packets and these packets are routed down. Finally, these packets are attached to the leaves PVW83,GMM96,GM97]. Reconstruction Phase. In a b ottom-up phase the packets attachedtothe leaves are really inserted and the tree is reconstructed. This reconstruction is based in just one unique wavemoving b ottom up. First, the packets are incorp orated at the b ottom internal no des of the tree. In successive steps the wavemoves up, decreasing the depth one unit at each time. The evolution of this unique wave needs the usage of rules so called MacroSplit rules (see Figure 1). To dene them wehave several p ossibilities. For instance, wecan take rules giving a maximum number of internal no des holding twokeys. Another p ossibility consists on generate a maximum numb er of no des with one key. The MacroSplit algorithm can b e seen as a \height level" description of the well known parallel insertion algorithm given byW.Paul, U. Vishkin and H. Wagener in PVW83], whose reconstruction phase has b een rened (in order to avoid concurrent readings). This renement take place splitting a MacroSplit step into several more basic steps chained together in a pip eline. 3 Qualitative b ehavior of insertion algorithms In the further sections we will develop the fringe analysis of the MacroSplit insertion algorithm. Based on this analysis we can try a qualitative explanation 2
fe h ik hfbjd Split i) ii) a bcdefghi j k adg k cbj i aceg Fig. 1. Wehaveseveral choices for a MacroSplits Rule. In case ( i ) the rule creates a maximum numb er of double no des. In ( ii ) the rule creates the minimum numb er. Other intermediate strategies are also allowed. of parallel insertion algorithms. As usual fringe analysis deals only with the distribution of the b ottom insertion no des. We will prove that in the parallel case a fraction of no des having twoleaves can b e well approximated by a constant(like in the sequential case). It seems reasonable to assume that higher order fringe analysis for parallel algorithms will give close results (in the sequential case, this has b een exp erimentally tested by R. Baeza-Yates and P.Poblete in BYP95]). MacroSplit algorithms. Let us assume that the 2-3 tree has n no des and k is the number of keys to b e inserted. Assume k indep endentof n .From the preceding remarks the exp ected number of levels aected bya wave is logarithmic on k . This happ ens b ecause at every level it seems that a constant fraction c 1 = 3ofkeys will not pro duce further actions. The same seems to happ en when k = o ( n ). Pip elines based algorithm. Eachwave of the pip eline parallel algorithm has an exp ected logarithmic life time on k b ecause the time sp entateachlevel is constant. Then we can take advantage of this fact in the following two senses: 1. Assume that wehave p pro cessors and k keys with p< k . Then the rst wave starts with p pro cessors managing p keys. When the second wave starts, the rst one only has a part cp of active pro cessors b ecause 1 ; cp ones have inserted its key and are now free. Then the second wave starts with 1 ; cp pro cessors and so on. Therefore, the exp ected number of pro cessors needed to insert the k keys can b e reduced to O ( k= log k ). 2. Assume nowthatwehave p> k pro cessors and that eachwave starts with k pro cessors. The second wave only needs ck new pro cessors b ecause the remainder 1 ; ck are those left free by the rst wave, and so on. Therefore, a stationary pro cess of pip elined waves, where each of them inserts k keys, can b e supp orted with k = O ( p ) pro cesses. Much more research has to b e done in order to prove mathematically the preceding assertions. To justify them let us start with a precise fringe analysis. 3
4 Fringe analysis for parallel insertions The fringe of a tree is comp osed by the subtrees on the last level. A no de with one key is designated x no de, and a no de with twokeysisan y no de. Note that b ottom no des separate leaves into 1 ; ty pe leaves if their parents are x no des otherwise, 2 ; ty pe leaves. When a new element falls in a no de of typ e x ,is transformed in a no de of typ e y . Otherwise, a no de of typ e y is split into two new x no des. Let X t and Y t b e the random variables asso ciated to the number of 1 ; ty pe leaves and 2 ; ty pe leaves resp ectively at the step t .We assume X t + Y t = n + 1 b eing n the numberofkeys of the tree. The exp ected number of leaves (conditioned to the random insertion of one key) at the step t can b e mo deled byEZG + 82]: E ( X t +1 j 1) E ( Y t +1 j 1) = T n 1 E ( X t j 1) E ( Y t j 1) where T n 1 is the transition matrix T n 1 = 1+ 1 n +1 I + 1 n +1 H b eing I = 10 01 and H = ; 34 3 ; 4 : The probability that a random chosen leaf b elongs to the i ; ty pe is: P i = Exp ected numb er of leaves of i ; ty pe Numb er of leaves of the tree : Then the insertion pro cess implies the stationary values of the probabilityfor P 1 =4 = 7and P 2 =3 = 7. More details can b e found in BY95]. We consider now that k keys are in a random parallel manner inserted into a tree of size n with X t (resp ectively Y t ) leaves of 1 ; ty pe (2 ; ty pe ). The exp ected values of the random variable X t +1 and Y t +1 after the insertions dep ends on the exp ected values of X t and Y t only. This means that the currentvalue dep ends on the history of the pro cess only through the most recentvalue. Therefore wedeal with a Markovchain and the evolution can b e analyzed through a recurrence of the conditional exp ectations given by E ( X t +1 j k ) E ( Y t +1 j k ) = T nk E ( X t j k ) E ( Y t j k ) : where T nk is as b efore the transition matrix. The transition matrix is computed by considering a uniform distribution of keys and the transformation of the b ottom no des. Let us explain this last p oint. Assume that k keys have b een inserted, then, at most, k keys can reach a no de. If the no de stores more than twokeys, it must b e split. Table 1 shows some splits of x and y no des for instance, the rst row shows the x no de transformation into an y and the y no de transformation into xx no des under the one key insertion, and the fourth rowshows how x and y no des with new four keys can b e split 4
k x no de y no de 1 yxx 2 xx xy 3 xy xxx or yy 4 xxx or yy xxy 5 xxy xxxx or xy y 6 xxxx or xy y xxxy or yyy Table 1. Transformation of x and y b ottom no de once k keys reachthem n 123 4 5 6 7 8 9 10 31 41 51 k =11 0 1 .4 .6 .5714=4/7 k =21 1 .5 .5625 5609 .5689 .5702 .5706 k =31 .4 .466 .5394 .5656 .5687 .5697 Table 2. Probabilityof1 ; ty pe leaves once k keys have b een inserted rep eatedly (in some cases there are dierent p ossibilities). Note that y no de transformation when k keys reach it is the same as the x no de transformation when k +1 keys reach it. The columns of Table 2 show the exp erimental evolution of the probalility values of 1 ; ty pe leaves (the initial tree had one x no de). Note that these values rapidly converge to 4 = 7, therefore this value seem to b e an upp er limit in the parallel case. The same table shows that the parallel insertion determines a leaves distribution dierent than those determined by sequential insertions. Wedevelop next the parallel insertion of twokeys. We follow the same technique applied b efore to sequential insertions EZG + 82]. 4.1 Parallel insertion of twokeys Assume that wehave a tree with n keys and X t Y t leaves of eachtyp e with X t + Y t = n +1. We insert randomly in parallel two additional keys. Then, the exp ected numberofleaves is given by E ( X t +1 j 2) E ( Y t +1 j 2) = T n 2 E ( X t j 2) E ( Y t j 2) : These twokeys fall through the tree until they reach b ottom no des. As at most twokeys can reach the same b ottom no de, wehave no election in the split, i.e. the transformation of b ottom no des is unique (second row of table 1). Both keys can b e either at the same b ottom no de or at dierent b ottom no des, and in each case b ottom no des can b e of typ e x or y . Let P ( x x ) b e the probabilitythat b oth keys reach the same x no de, P ( x 1 x 2 ) the probabilityto reach dierent x no des and so on for the remainder probabilities P ( x y ) and P ( y 1 y 2 ). Wedenote the generic case as P ( ), b eing ( : : ) the generic pair of no des accessed. 5
( ) P ( ) E ( X t +1 j X t Y t 2 ( : : )) E ( Y t +1 j X t Y t 2 ( : : )) ( x x ) X t n +1 2 n +1 X t +2 Y t ( x 1 x 2 ) X t n +1 X t ; 2 n +1 X t ; 4 Y t +6 ( x y ) 2 X t n +1 Y t n +1 X t +2 Y t ( y y ) Y t n +1 3 n +1 X t +2 Y t ( y 1 y 2 ) Y t n +1 Y t ; 3 n +1 X t +8 Y t ; 6 Table 3. Parallel insertion of twokeys The exp ected number of 1 ; ty pe leaves is: E ( X t +1 j X t Y t 2) = X ( ) P ( ) E ( X t +1 j X t Y t 2 ( : : )) b eing E ( X t +1 j X t Y t 2 ( : : )) the exp ected number of 1 ; ty pe leaves when two keys reachnode( ) conditioned to initial exp ected number of leaves X t and Y t . For instance, if b oth keys reach dierent x no des then it holds P ( x 1 x 2 )= X t n +1 X t ; 2 n +1 : The exp ectations of 1 ; ty pe leaves is E ( X t +1 j X t Y t 2 ( x 1 x 2)) = X t ; 4 : Table 3 contains the other values. Moreover E ( X t +1 j 2) = E ( E ( X t +1 j X t Y t 2)) Lemma 1. The transition matrix T n 2 is 1+ 2 n +1 I + 2 n +1 H + ; 1 ( n +1) 2 ; 12 18 12 ; 18 being H = ; 34 3 ; 4 Proof. We compute the conditional exp ectation only for X t +1 (the Y t +1 term has a similar development). Then E ( X t +1 j X t Y t 2) is: X ( ) P ( ) E ( X t +1 j X t Y t 2 ( :: )) = 1 ( n +1) 2 2 X t ( X t +2)+ X t ( X t ; 2)( X t ; 4) + 2 X t Y t ( X t +2) +3 Y t ( X t +2) + Y t ( Y t ; 3)( X t +8) = X t + 1 ( n +1) 2 12 X t ; 4 X 2 t +4 X t Y t +8 Y 2 t ; 18 Y t ) = 1 ; 4 n +1 + 12 ( n +1) 2 X t + 8 n +1 ; 18 ( n +1) 2 Y t This concludes the pro of. ] 6
4.2 Computation of the transition matrix of the k keys insertion Assume that we insert k 1 additional keys on a tree with X t leaves of 1 ; ty pe and Y t of 2 ; ty pe .We select one key and denote it .This key can reacha b ottom no de x or y the rst case is denoted case and the second one case. Then the exp ectations of 1 ; ty pe leaves after the insertion are given by E ( X t +1 j X t Y t k )= P ( ) E ( X t +1 j X t Y t k ; 1 )+ P ( ) E ( X t +1 j X t Y t k ; 1 ) where E ( X t +1 j X t Y t k ; 1 ) is the exp ected numberof1 ; ty pe leaves once k keys have b een inserted and one of them, , has reachan x no de. Similarlyfor E ( X t +1 j X t Y t k ; 1 ). Clearly P ( )= X t n +1 and P ( )= Y t n +1 : If key reaches an x b ottom no de, then the probability that i keys of the remainder k ; 1 ones reach the same no de is b i k ; 1 2 n +1 = k ; 1 i 2 n +1 i 1 ; 2 n +1 k ; 1 ; i : Then the exp ected values can b e dened recursively as: E ( X t +1 j X t Y t k ; 1 )= k ; 1 X i =0 b ( i k ; 1 2 n +1 ) E ( X t +1 j X t ; 2 Y t k ; 1 ; i )+ X xi +1 E ( X t +1 j X t Y t k ; 1 )= k ; 1 X i =0 b ( i k ; 1 3 n +1 ) E ( X t +1 j X t Y t ; 3 k ; 1 ; i )+ X yi +1 : The term X xi +1 is the number of 1 ; ty pe leaves after the insertion of i +1 keys into an x no de. In the same way, the term X yi +1 is the number of 1 ; ty pe leaves after the insertion of i +1 keys into an y no de (For 2 ; ty pe leaves wehave Y xi +1 and Y yi +1 ). For instance, the second row of table 1 shows that X x 2 =4 and X y 2 =2. Theorem 2. The expectednumber of 1 ; ty pe and 2 ; ty pe leaves after the random insertion of k keys into a tree with X t +1 leaves of 1 ; ty pe and Y t +1 of 2 ; ty pe are given by E ( X t +1 j k ) E ( Y t +1 j k ) = T nk E ( X t j k ) E ( Y t j k ) : 7
with T nk is the transition matrix T nk = 1+ k n +1 I + k X j =0 ( ; 1) j ( n +1) j k j j ; j ; j j where j = ; 2 j ; 1 j X i =0 ( ; 1) i j i Y xi and j = ; 3 j ; 1 j X i =0 ( ; 1) i j i X yi : The pro of is given in the app endix. From this transition matrix and using the fact that the probabilities can b e dened as ;;;! P t +1 k = E ( X t +1 j k ) n +1+ k E ( Y t +1 j k ) n +1+ k it is p ossible to have a recurrence in one variable, obtaining that for constant k and asymptotically in the number of keys n , ;;! P t +1 =4 = 7 3 = 7] + O ( k=n ). The ab ove seems to b e true for any k of o ( n ). 5 Approximated Analysis Motivated by the complexity of the exact analysis of the generic case of k insertions, we presenttwo approximated analysis. The rst one approaches the distribution with a binomial. The second approximation considers k sequential insertions. The two approximations give go o d results for n>> k . Binomial approximation. Let X t Y t b e the currentnumber of leaves. Assume that r keys reachan x b ottom no de and k ; r keys and y b ottom no de with probability ; k r p r q k ; r being p = X t n +1 and q = Y t n +1 . Then, the new state is determined by X t +1 Y t +1 = X t Y t + k r p r q k ; r r ; 2 3 +( k ; r ) 4 3 : Note that E ( p )= E ( X t n +1 )= p 1 ( n ) and E ( q )= p 2 ( n ). Lemma 3. It holds E ( X t +1 )= E ( X t ) ; 6 kp 1 ( n )+ 4 k and for n 6 , E ( X t )= 4 7 ( n +1) . Proof. E ( X t +1 )= E ( E ( X t +1 j X t Y t )) = E P k r =0 ( x n ; 6 r +4 k ) ; k r p r q k ; r : ] The transition matrix in the binomial approximation is: T bin nk = 1+ k n +1 I + k n +1 H b eing H = ; 34 3 ; 4 8
Lemma 4. It holds Var ( X t +1 )= 1 ; 12 k n +1 Var ( X t )+ 6 2 k ( k ; 1) ( n +1) 2 Var ( X t )+ 6 2 kp 1 ( n ) p 2 ( n ) and for n 6 the asymptotic expression of Var ( X t ) is 12 13 6 7 2 ( n +1) 1+ 6 2 12 k ; 1 n +1 + 6 4 12 11 k ; 1 n +1 2 + 6 4 ( k ; 1) 2 (35 k ; 36) 12 11 10 ( n +1) 3 + O ( n ; 4 ) : This lemma can b e proved by usual techniques. Using this approximation, the variance of the parallel insertions has the same rst order term of the sequential one BP85]. Sequential approximation. Like the transition matrix can b e written as T n 1 = 1+ 1 n +1 I + 1 n +1 ; 34 3 ; 4 = n +2 n +1 I + 1 n +2 H the transition matrix to insert sequentially k keys (one after another), dened by the comp osition T seq ( n k )= T n + k ; 1 1 T n 1 , is equal to T seq ( n k )= n + k +1 n +1 I + 1 n + k +1 H I + 1 n + k H I + 1 n +2 H : Lemma 5. The transition matrix T seq ( n k ) is (with c k 1 = k ): 1+ k n +1 I + c k 1 n +1 H + c k 2 ( n + k )( n +1) H + c k 3 ( n + k )( n + k ; 1)( n +1) H + This expression allow us to guess the form of the transition matrix for the parallel case T nk = T seq ( n k )+ I O 1 n 2 : Therefore, parallelizing the insertions only changes second order terms with resp ect to the sequential case. 6 Final Remarks and Future Work Our results show that the parallel insertion of a constantnumber of keys do es not dier signicantly from the sequential case. This result is intuitive, although we have seen that was not easy to prove. Wehave analyzed a parallel and sequential approximations, and the two cases diers from the exact analysis in the second order term, b eing equal the rst terms. Our analysis can b e also applied to AVL trees and other balanced search trees with minor changes (that is, the analysis of the fringe). Further work implies the use of our results to do a b etter p erformance study of distributed parallel algorithms, as shown in section 3. 9