A Hybrid Solution of Fork/Join Synchronization in Parallel Queues
A Hybrid Solution of Fork/Join Synchronization in Parallel Queues
复制标题
并行队列中Fork/Join同步的混合解决方案
DOI：
10.1109/71.946659
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
R. Chen
中科院分区：
文献类型：
--
作者：
R. Chen
针对 K/spl ges/2 的通用 K 队列先进先出 HFJ（同质 fork/join 排队）系统引入了一种新的分析技术，即动态冒泡排序分析。动态冒泡排序模型根据每个分支中等待同步的任务数量对队列的分支进行动态排序。工作以平均速率 /spl lambda/ 和一般到达分布到达。到达后，作业会分成 K 个任务。任务k，k=1,2,...,K，被分配给第k个排队系统，该系统是一个先进先出的服务器，具有一般的服务分配和无限容量的队列。一旦所有任务完成服务，作业就会离开 HFJ 系统。换句话说，对应于同一作业的任务在离开 HFJ 系统之前会被合并。我们获得了一个通用且简单的混合解决方案，该解决方案结合了平均响应时间的分析和模拟，我们用 T/sub K/ 表示。我们获得了一个非常简单的（仅作为 T/sub 1/ 和 T/sub 2/ 的函数）和 T/sub K/ 的一般上限表达式，并且我们获得了 K=2 和 3 的情况之间的精确关系。我们通过模拟 p=0.1、0.2、....0.8 和 0.9 的 2、3、...、99 和 100 个队列来评估我们的结果，每个队列针对四种不同的 HFJ 情况，其中 /spl rho/=/spl lambda///spl mu/ 和 /spl mu/ 是服务器的平均任务服务率。我们的混合解决方案与所有模拟的最大绝对偏移小于 0.33% (1/300)，这是一个合理的模拟误差率。所有模拟的上限的最大偏移量是 21%。
A new analysis technique, dynamic-bubblesort analysis, is introduced for general K-queue first-in-first-out HFJ (homogenous fork/join queuing) systems of K/spl ges/2 . The dynamic-bubblesort model dynamically sorts the branches of the queues based on the number of the tasks waiting for synchronization in each branch. Jobs arrive with mean rate /spl lambda/ and a general arrival distribution. Upon arrival, a job forks into K tasks. Task k, k=1, 2, ..., K, is assigned to the kth queuing system, which is a first-in-first-out server with a general service distribution and an infinite capacity queue. A job leaves the HFJ system as soon as all its tasks complete their service. In other words, tasks corresponding to the same job are joined before departing the HFJ system. We obtain a general and simple hybrid solution which combines analysis and simulation for the mean response time that we denote by T/sub K/. We obtain a very simple (as a function of T/sub 1/ and T/sub 2/ only) and general upper bound expression for T/sub K/ and we get an exact relationship between the cases for K=2 and 3. We evaluate our results by simulating 2, 3, ..., 99, and 100 queues for p=0.1, 0.2, ....0.8, and 0.9, each for four different HFJ cases, where /spl rho/=/spl lambda///spl mu/ and /spl mu/ is the average task service rate for a server. The maximum absolute offset for our hybrid solutions from all the simulations is less than 0.33 percent (1/300), which is a reasonable error ratio for simulation. The maximum offset for our upper bounds over all the simulations is 21 percent.