- 上一篇：模具快速制造技术英文文献和中文翻译
- 下一篇：连续密集查询计划正式溢出策略评估英文文献和中文翻译
During the first pass, how-ever, if all the sorters are inputing items simultaneously andusing the same set of node values to generate the subtrees, twoor more sorters may have to store items in the same subtree orthe same memory simultaneously.If each memory contains a queuing mechanism for ac-cepting and storing items which arrive simultaneously, it canbe shown that the main queue length Lq is given by [7]Lq = Sp[2 - (S + l)p]/[2(l - Sp)]where p is the probability of inserting an item in a memory.(It should be noted that his formula for Lq is the same whethersimultaneous or -asynchronous arrivals are a-sumed; all thatis necessary is that the arrivals occur during the same timeinterval.) If S memories are assumed, then the probability pis equal to 1/S and the value of Lq is unbounded. If 2Smemories are assumed, then the probability p is equal to 1/(2S) and the value of Lq is between 0.5 and 0.75 dependingupon the value of S. This is a small enough queue size to causeno difficulties, so we assume that there are 2S memories, eachwith a queuing mechanism, and that all the memories are ac-cessible by every sorter, which implies the existence of an in-terconnection network of some kind.While the network connecting the sorters and memories canbe of seveiLal types, the memories are assumed here to bemultiport memories with one port for each sorter. The overallarchitecture is shown in Fig. 2. This choice avoids communi-cation problems at the cost of introducing a queueing mech-anism in each memory. However, the parallel sorting approachcan also be adapted in a local computer network environment.In which case, rather than memory contention, the problemof I/O and communication overhead must be addressed.To determine the effect of multiple memories on the size ofthe list which can be sorted, assume the sublists are stored in IEEE TRANSACTIONS ON COMPUTERS, VOL. C-32, NO. 7, JULY 1983Fig. 2. A multiport memory architecture for the PBT.m memories so that each memory contains b/m sublists. (Tosimplify the algebra that follows, assume that m pides bexactly.) The expected total length of the b/m sublists is bu/mwhere u is the expected length of a single sublist, the varianceof the total length of the b/m sublists is bs2/m where s2, andthe variance of the length of a single sublist iss2 = [(N-b- I)N(b- 1)]/[b2(b + 1)].By the central limit theorem, the distribution of the totallength of the b/m sublists approaches a normal distributionwith mean bu/m and variance bs2/m as b/m becomes un-bounded; when b/m > 25, the approximation is close enoughfor our use, so assume b/m > 25 and the total length of thesublists is normally distributed. Then the probability that thetotal length exceeds M, the storage capacity of a singlememory, can be computed from u and s. In particular, theprobability that the length differs from the mean by more thanfive standard deviations is 0.00005; thus, the probability thatthe total length of the sublists exceeds M is less than 0.000025whenM> [bu/m] + 5[b/M]0.5s.When N >> b, the case of interest here, u _ s _ N/b. Sub-stituting this into the last inequality and simplifying givesN < mM/[l + 5(m/b)0.5].Since mM is the total memory capacity of the system, the sizeof the sublist which can be sorted is reduced by the factor [1+ 5(m/b)05]- I when the memory is subpided into m inde-pendent parts. The factor is a decreasing function of m/b; itsmaximum value is one (when m/b = 0) and it decreases to 0.5when b/m = 25. Thus, values of b should be greater than 25mif large lists are to be sorted without requiring inordinateamounts of memory or paging. Further increases in b do notaffect the factor as much; for example, changing b to lOOmchanges the factor from 0.5 to 0.67. Since the queue charac-teristics require that m = 2S, b > 25m is equivalent to b >SOS.During the first pass, the buckets must also have a queuingmechanism if conflicts are to be avoided. Furthermore, eachmemory needs a counter if the incoming items are to be storedsequentially. These requirements can be met if each memorymodule contains a bucket memory and a counter besides thequeueing mechanism and storage space for the items and links.Essentially a sorter is split into two parts: a distributor whosealgorithm for the first pass isInitialize: I = 0Set all node values equal to infinityRepeat for each itemIncrement I.Input item.Let B = Location of "nearest" node value