An application of program unification to priority queue vectorization

In this experimental study, we apply the technique of program unification to priority queues. We examine the performance of a variety of unified priority queue implementations on a Cray Y-MP. The scope of the study is restricted to determining if different implementations of priority queues exhibit markedly different performance characteristics under program unification. We found this to be true. In a larger view, this result has interesting consequences in the application of program unification to discrete event simulations on vector or SIMD machines. We find the heap to be a promising data structure in the program unification paradigm.This research was supported by the National Science Foundation under Grant No. ASC-9002225, and by NATO under Grant CRG 900108.Also supported in part by the Mathematical Sciences Section of Oak Ridge National Laboratory under contract DE-AC05-84OR21400 with Marietta Energy Systems, Inc.     

基于优先级队列的分布式多主题爬虫

在分布式环境中,为提高资源利用率和网页抓取效率,提出一种基于优先级队列的分布式多主题爬虫调度算法PQ‐MCSA。利用基于缓存的扩展式哈希算法对整体任务集进行切割,按照URL逻辑二级节点哈希映射法,将分割后的子任务集均匀地分配到各处理节点中;利用单处理节点的计算能力结合构建的任务优先级队列进行不同主题任务的调度。该算法改善了传统分布式爬虫对单节点的处理资源调度不充分、多主题任务爬取不均匀等缺点。实际项目的应用结果表明,使用该方法能够有效地提高各主题爬取结果的均衡度,具有较强的实用性。     

一种基于多级队列的并行区域生长算法

区域生长是经典的图像分割方法之一,为了满足图像分割的实时性要求,提出了一种基于多级队列的并行区域生长算法。该算法采用多级队列存放待生长的种子像素,优先生长边界种子像素,以尽快生成越界种子节点,从而减少邻居节点的等待时间。实验表明,该算法相比一般的基于单队列的算法,加速比有显著提高,且可扩展性较好。     

基于优先级队列的银行服务仿真系统

通过在银行营业服务现场收集的各种信息,对银行服务过程进行分析,提出银行客流随机变量的模拟方法,在此基础上通过优先级队列建立事件驱动的服务过程仿真模型.最后,用Microsoft Visual C 设计实现了仿真系统.计算机仿真实验表明,该系统达到预期的银行服务过程仿真的功能和技术要求,并且可以根据需要进一步完善其功能.事实上,该仿真模型具有一般意义.     

基于动态权值优先级队列的移动消息推送策略

针对传统的加权循环队列调度在移动消息推送平台中会增加系统开销、延长消息发送时间等问题,提出一种基于动态权值的加权循环调度策略.该策略在原有加权循环调度算法基础上,采用了动态权值策略,使得推送系统不再需要对消息的发送情况作额外的记录,有效降低了系统开销.对提出的算法进行了模拟实验,实验结果表明,改进的策略减少了消息发送的整体时延,提高了移动推送平台的消息发送效率.     

An efficient parallel strategy for the perfect domination problem on distance-hereditary graphs

A graph is distance-hereditary if the distance stays the same between any of two vertices in every connected induced subgraph containing both. Two well-known classes of graphs, trees and cographs, both belong to distance-hereditary graphs. In this paper, we first show that the perfect domination problem can be solved in sequential linear-time on distance-hereditary graphs. By sketching some regular property of the problem, we also show that it can be easily parallelized on distance-hereditary graphs.     

解优先级约束并行机调度问题的人工免疫算法

针对家纺企业车间调度的实际情况,建立了优先级特殊工艺约束下并行多机拖后调度模型,并提出一种新颖的人工免疫算法对其求解。该算法是依据生物的免疫机理,将目标函数作为抗原,将问题的解作为抗体,对抗体采用向量组编码的方式进行编码,通过克隆、变异及一种新颖的基于浓度的种群多样性更新选择方法,提高了种群多样性,并通过局部搜索改善了种群质量,加快了收敛速度。仿真结果表明,与遗传算法相比较,该算法能更快更准确地收敛到全局最优解。     

一种并行扫描计算局部调度算法

为了解决优先级调度算法的可扩展性问题,本文设计并实现了一种局部的深度优先扫描算法(PDFHDS)。该算法在计算初始优先级和计算最终优先级时,对每个结点只遍历一次,在这一次遍历中只访问该结点的全部直接前驱,避免了在PDFDS算法中每修改一个结点的优先级就要访问其全部前驱结点的情况,减少了一部分计算开销,消息传递过程使用单向传递,只向前邻处理器传递有多级外部后继的网格点信息,而不传递只具有一级外部后继的网格点信息,节省了通信开销。从实验数据可知,虽然在处理器个数少的时候性能比不上DFHDS算法,但对于多处理器的情况,PDFDS算法的性能可以比DFHDS算法的提高50%,甚至更多。     

解非等同并行多机调度问题的并行遗传算法

针对最小化完工时间的非等同并行多机调度一类问题,提出了一种混合遗传算法。该算法根据问题的特点,采用一种自然编码方案,此编码与调度方案一一对应,并对初始种群、交叉和变异等方法进行了研究。在鉴于遗传算法自然的并行性特点的基础上,实现了主从式控制网络模式下并行混合遗传算法。计算结果表明,并行混合遗传算法是有效的,优于启发式算法和遗传算法,有着较高的并行性,能适用于大规模非等同并行多机调度问题。     

基于GIS优化Dijkstra算法在物流中心选址中的研究*

基于传统的Dijkstra算法,提出了一种采用二叉堆结构和网络边存储模型的优化Dijkstra算法.实验结果表明:优化后的算法是切实有效的,将其应用到物流中心选址中得到了较满意的选址方案.     

并行数据库上的并行CMD－Join算法

并行数据库在多处理机之间的分布方法(简称数据分布方法)对并行数据操作算法的性能影响很大.如果在设计并行数据操作算法时充分利用数据分布方法的特点,可以得到十分有效的并行算法.本文研究如何充分利用数据分布方法的特点,设计并行数据操作算法的问题,提出了基于CMD多维数据分布方法的并行CMD－Join算法.理论分析和实验结果表明,并行CMD－Join算法的效率高于其它并行Join算法.     

An efficient implementation of parallel eigenvalue computation for massively parallel processing

This paper describes an efficient implementation and evaluation of a parallel eigensolver for computing all eigenvalues of dense symmetric matrices. Our eigensolver uses a Householder tridiagonalization method, which has higher parallelism and performance than conventional methods when problem size is relatively small, e.g., the order of 10,000. This is very important for relevant practical applications, where many diagonalizations for such matrices are required so often. The routine was evaluated on the 1024 processors HITACHI SR2201, and giving speedup ratios of about 2–5 times as compared to the ScaLAPACK library on 1024 processors of the HITACHI SR2201.     

T-preemptive priority queue and its application to the analysis of an opportunistic spectrum access in cognitive radio networks

We propose a new priority discipline called the T-preemptive priority discipline. Under this discipline, during the service of a customer, at every T time units the server periodically reviews the queue states of each class with different queue-review processing times. If the server finds any customers with higher priorities than the customer being serviced during the queue-review process, then the service of the customer being serviced is preempted and the service for customers with higher priorities is started immediately. We derive the waiting-time distributions of each class in the M/G/1 priority queue with multiple classes of customers under the proposed T-preemptive priority discipline. We also present lower and upper bounds on the offered loads and the mean waiting time of each class, which hold regardless of the arrival processes and service-time distributions of lower-class customers. To demonstrate the utility of the T-preemptive priority queueing model, we take as an example an opportunistic spectrum access in cognitive radio networks, where one primary (licensed) user and multiple (unlicensed) users with distinct priorities can share a communication channel. We analyze the queueing delays of the primary and secondary users in the proposed opportunistic spectrum access model, and present numerical results of the queueing analysis.     

A parallel algorithm for approximate regularity

Spatial regularity amidst a seemingly chaotic image is often meaningful. Many papers in computational geometry are concerned with detecting some type of regularity via exact solutions to problems in geometric pattern recognition. However, real-world applications often have data that is approximate, and may rely on calculations that are approximate. Thus, it is useful to develop solutions that have an error tolerance.

A solution has recently been presented by Robins et al. [Inform. Process. Lett. 69 (1999) 189–195] to the problem of finding all maximal subsets of an input set in the Euclidean plane that are approximately equally-spaced and approximately collinear. This is a problem that arises in computer vision, military applications, and other areas. The algorithm of Robins et al. is different in several important respects from the optimal algorithm given by Kahng and Robins [Patter Recognition Lett. 12 (1991) 757–764] for the exact version of the problem. The algorithm of Robins et al. seems inherently sequential and runs in O(n^5/2) time, where n is the size of the input set. In this paper, we give parallel solutions to this problem.     

基于HRR划分的并行RDB~n树Join算法

文章首先介绍了PDBMS采用的Hash-Round-Robin(HRR)数据划分方法以及基于该划分方法的并行RDBn树,最后着重、详细地给出了基于该树的并行Join算法,分析了该算法的效率。     

ETL工作流活动优先级的确定及并行实现*

ETL流程是一个以数据为中心的工作流,对ETL工作流的执行过程进行论述,提出了一个算法,计算ETL工作流中各个活动的执行优先级,在工作流执行中为优先级相同且相互之间没有依赖关系的活动集创建多个线程,通过并行执行这些活动,提高了ETL工作流的执行效率。实验结果表明,所提出的并行算法与串行算法比较,在数据量足够大的情况下,加速比可接近理想值,加速比随着数据量增大而提高。     

A computational model for static data flow machines

Computer architects have been constantly looking for new approaches to design high-performance machines. Data flow and VLSI offer two mutually supportive approaches towards a promising design for future super-computers. When very high speed computations are needed, data flow machines may be relied upon as an adequate solution in which extremely parallel processing is achieved.

This paper presents a formal analysis for data flow machines. Moreover, the following three machines are considered: (1) MIT static data flow machine; (2) TI's DDP static data flow machine; (3) LAU data flow machine.

These machines are investigated by making use of a reference model. The contributions of this paper include: (1) Developing a Data Flow Random Access Machine model (DFRAM), for first time, to serve as a formal modeling tool. Also, by making use of this model one can calculate the time cost of various static data machines, as well as the performance of these machines. (2) Constructing a practical Data Flow Simulator (DFS) on the basis of the DFRAM model. Such DFS is modular and portable and can be implemented with less sophistication. The DFS is used not only to study the performance of the underlying data flow machines but also to verify the DFRAM model.     

Faster optimal parallel prefix circuits: New algorithmic construction

Parallel prefix circuits are parallel prefix algorithms on the combinational circuit model. A prefix circuit with n inputs is depth-size optimal if its depth plus size equals 2n-2. Smaller depth implies faster computation, while smaller size implies less power consumption, less VLSI area, and less cost. To be of practical use, the depth and fan-out of a depth-size optimal prefix circuit should be small. A circuit with a smaller fan-out is in general faster and occupies less VLSI area. In this paper, we present a new algorithm to design parallel prefix circuits, and construct a class of depth-size optimal parallel prefix circuits, named SU4, with fan-out 4. When n30, SU4 has the smallest depth among all known depth-size optimal prefix circuits with fan-out 4.     

一种生成动态随机数的并行算法

针对软件难以生成高质量随机数的问题,提出一种基于并行结构的随机数生成算法。该算法采用关联系统和数据缓冲机制,利用读过程和写过程的时间差值实现对缓冲区域数据的动态化,提高了随机数质量。测试该算法生成的随机序列,结果表明在NIST800—22标准下,其通过率大于99．7％。