基于深度优先贪婪搜索的可重构硬件任务划分算法

针对可重构计算硬件任务划分通信成本较小化的问题,提出了一种基于深度优先贪婪搜索划分(DFGSP)算法。首先,从待调度的就绪队列中取出队首任务,在某一硬件面积约束下,按深度优先搜索(DFS)方式扫描一个计算密集型任务转换来的有向无环图(DAG),逐个划入满足要求的节点;然后,一遇到不满足面积要求的任务节点时,就计算当前划分模块间输出边数(可量化为通信成本);最后,跳过当前不满足要求的任务节点,继续搜索该点之后处于就绪状态的节点,当搜索到满足要求的点时,按加入该点后不增加当前划分块间输出边数和尽可能填满可重构运算阵列的原则进行。实验结果表明,与现有的簇划分(CBP)、簇层次敏感两种划分算法相比,提出的算法获得了最小划分模块数和平均跨模块间I/O边数最小的均值,通过实际验证,算法显著地改善了硬件任务的划分效果,而且运行开销没有明显增加。     

考虑通信成本和硬件碎片利用的簇划分算法

针对面积约束下的可重构硬件任务划分问题,提出一种通信成本和硬件碎片利用的簇划分算法.根据簇划分算法的思想,在某一硬件面积的约束下,从待调度的就绪队列中节点依次划入到当前块,在划分过程中,若遇到不满足要求的节点就跳过,并继续搜索可划入到当前块且没有增加块间边数的节点.每划入一个节点就更新其后继的入度,如果入度为0且满足要求,将其直接划入;否则动态考查其前驱,如果前驱所需的面积满足规定的阈值,则将该节点后继和前驱一并划入到当前块.通过充分考虑节点权值、节点间的依赖度、层次小的节点优先划入等因素构造响应比函数,以动态地调整就绪列表节点的调度次序.实验结果表明,与簇划分算法和簇层次敏感划分算法相比,文中算法在划分块间非原始I/O次数、划分块数等方面均获得了较好的改进;在减少块间通信成本方面,该算法具有合理性和可行性.     

基于并行度最大化的多目标优化任务划分算法

针对可重构系统硬件任务划分并行度最大问题,提出一种基于并行度最大的多目标优化任务划分算法。首先,该算法在满足可重构硬件面积资源和合理依赖关系的约束下,按广度优先的遍历方式搜索待划分的操作节点;然后,着重考虑执行延迟对于系统完成时间的影响,将块内操作节点的并行度最大化;最后,在减少碎片面积和不增加块间连接边数的原则下接受新的节点,否则就结束一个块划分。实验结果表明,与现有的基于层划分（LBP）和基于簇划分（CBP）两种算法相比,提出的算法获得了最大的块内操作并行度,同时还减少了划分块数和块间的连接边数。     

基于分层聚类和干扰对齐的MIMO链路调度算法

为了降低干扰对齐所需的处理开销,将链路划分为多个簇分别进行处理成为可行的办法之一。针对现有簇划分算 法中运算复杂度较高的问题,本文提出了一种基于最小信干比的簇划分算法。在此基础上,针对所有簇同时通信造成部分簇内链路接收端信干噪比（Signal to interference plus noise ratio,SINR）较低的问题,本文将以链路为单位的调度问题等效为以簇为单位的调度问题,提出了一种基于层次聚类的簇调度算法。理论与仿真实验结果表明,本文所提出的簇划分算法的运算复杂度明显低于现有算法,且相同条件下的系统平均吞吐量更高。同时,本文提出的基于簇层次聚类的调度算法不同程度地提升了各簇内链路接收端的SINR,系统可根据不同的性能需求进行调度策略选择。     

模块度引导下的社区发现增量学习算法

当前社区发现领域存在诸多静态社区划分算法,而其划分结果的不稳定性和较高的算法复杂度已经不能适应如今规模庞大,变化频繁的网络结构。为解决传统静态算法这一局限性,提出了一种利用模块度优化的增量学习算法,将网络结构的变化划分成边变化、点变化两种基本操作,在对"模块度最大化"的规则指导下实现网络结构的增量学习。实验表明,该算法在保证原有社区划分结果的前提下,可以将新变化的节点快速划分进已有社区,并使得模块度与静态算法重新计算模块度相近,节省了时间,保持了社区划分的实时性。     

通用的层次化FPGA划分算法

层次化FPGA（HFPGA）是目前工业主流的芯片架构.在前人关于HFPGA成果的基础上,提出了一种改进的划分算法.该算法将模拟退火算法与ratio-cut思想结合,确定多层多划分的规模后,采用数据结构进行多分优化,在将可配置逻辑块（configurable logic block,CLB）划分到各个簇的时候考虑割线数的目标函数,实现了更好的划分结果,提高了FPGA芯片的利用率,优化了整个芯片的性能.     

基于适应度的簇划分算法研究

延长网络生存期、减少网络能量消耗是传感器网络一项重要性能指标,分簇方案是实现该目标的主要方法之一.通过分析影响簇状网能耗的主要能耗参数,引入节点适应度模型,并该模型运用到簇划分算法中,优化网络能量效率.算法是分布式簇划分算法,在簇划分过程中,通过比较节点局部区域能量比、通信代价比、节点度数综合能耗因素,决定簇首节点和成簇规模.仿真结果表明该算法能够降低簇间的通信重叠,均衡网络负载,与几种算法比较适应度分簇算法使网络生存时间增加的幅度虽然不是很大,但是使网络系统的稳定时间比其他2种能量有效的算法延长了近20%左右.     

数字电路门级并行逻辑模拟

对基于事件驱动的电路门级并行逻辑模拟算法和相应的电路划分算法进行了研究。在保守协议的基础上,模拟算法采用流水线技术避免了死锁;采用事件打包,消息队列和非阻塞通讯技术减少了消息传递开销。在聚集分解的基础上,电路划分算法对组合或时序电路都可进行非循环划分,保证流水线模拟不会出现死锁。在曙光集群上采用MPI实现了模拟算法,对ISCAS部分电路进行实验,获得了很好的加速比。最后提出采用预模拟方法的电路划分改进方案。     

大图结构特征对划分效果的影响

针对大图结构特征如何影响划分效果这一问题,提出一种通过顶点度分布特征来描述大图结构特征的方法。首先,基于真实的图数据产生若干顶点数和边数相同、但结构特征不同的仿真数据集,通过实验计算真实图与仿真图之间的相似度,证明该方法对描述真实大图结构特征的有效性。然后,通过Hash和点对交换划分算法,验证图结构特征与划分效果之间的关系。当点对交换划分算法执行到5万次时,划分一个有6301个顶点和20777条边的真实图其交叉边数比Hash划分算法降低了54.32%,划分仿真图数据集中结构特征差异明显的两个图时,交叉边数分别为6233和316。实验结果表明,点对交换划分算法能够减少交叉边数,图的顶点度分布差异越大,划分后交叉边数越少,划分效果越好,因此大图结构特征影响其划分效果,这为建立图的结构特征与划分效果之间的关系模型研究奠定了基础。     

多级划分算法的后处理与评价方法

多级划分算法需要进行多次实验以得到最优值.本文根据网表顶点在多次实验中的倾向性将其分为:活跃点、固定点和亚固定点,并提出只对活跃点重新划分的后处理方法.另外,通过将固定点和亚固定点分配到相应簇中,得到一种算法评价方法.实验表明,本文的后处理方法可有效减小hMetis算法的最小割,而评价方法能够客观评价hMetis算法在不同聚类策略下的划分结果.     

Efficient algorithms for a class of partitioning problems

We address the problem of optimally partitioning the modules of chain- or tree-like tasks over chain-structured or host-satellite multiple computer systems. This important class of problems includes many signal processing and industrial control applications. Prior research has resulted in a succession of faster exact and approximate algorithms for these problems. We describe polynomial exact and approximate algorithms for this class that are better than any of the previously reported algorithms. Our approach is based on a preprocessing step that condenses the given chain or tree structured task into a monotonic chain or tree. The partitioning of this monotonic task can then be carried out using fast search techniques     

Algorithms and Support for Horizontal Class Partitioning in Object-Oriented Databases

Horizontal partitioning is a logical database design technique which facilitates efficient execution of queries by reducing the irrelevant objects accessed. Given a set of most frequently executed queries on a class, the horizontal partitioning generates horizontal class fragments (each of which is a subset of object instances of the class), that meet the queries requirements. There are two types of horizontal class partitioning, namely, primary and derived. Primary horizontal partitioning of a class is performed using predicates of queries accessing the class. Derived horizontal partitioning of a class is the partitioning of a class based on the horizontal partitioning of another class. We present algorithms for both primary and derived horizontal partitioning and discuss some issues in derived horizontal partitioning and present their solutions. There are two important aspects for supporting database operations on a partitioned database, namely, fragment localization for queries and object migration for updates. Fragment localization deals with identifying the horizontal fragments that contribute to the result of the query, and object migration deals with migrating objects from one class fragment to another due to updates. We provide novel solutions to these two problems, and finally we show the utility of horizontal partitioning for query processing.     

知识图谱划分算法研究综述

知识图谱是人工智能的重要基石,因其包含丰富的图结构和属性信息而受到广泛关注.知识图谱可以精确语义描述现实世界中的各种实体及其联系,其中顶点表示实体,边表示实体间的联系.知识图谱划分是大规模知识图谱分布式处理的首要工作,对知识图谱分布式存储、查询、推理和挖掘起基础支撑作用.随着知识图谱数据规模及分布式处理需求的不断增长,...     

Optimal Data-Space Partitioning of Spatial Data for Parallel I/O

It is desirable to design partitioning methods that minimize the I/O time incurred during query execution in spatial databases. This paper explores optimal partitioning for two-dimensional data for a class of queries and develops multi-disk allocation techniques that maximize the degree of I/O parallelism obtained in each case. We show that hexagonal partitioning has optimal I/O performance for circular queries among all partitioning methods that use convex non-overlapping regions. An analysis and extension of this result to all possible partitioning techniques is also given. For rectangular queries, we show that hexagonal partitioning has overall better I/O performance for a general class of range queries, except for rectilinear queries, in which case rectangular grid partitioning is superior. By using current algorithms for rectangular grid partitioning, parallel storage and retrieval algorithms for hexagonal partitioning can be constructed. Some of these results carry over to circular partitioning of the data—which is an example of a non-convex region.     

Partitioning and mapping in embedded multiprocessor architectures in the presence of constraints

The paper focuses on the problem of partitioning and mapping parallel programs onto heterogeneous embedded multiprocessor architectures for real-time applications. Such applications present unique constraints and challenges. In addition to heterogeneity, the proposed partitioning and mapping algorithms satisfy memory, task throughput, task placement, intertask communication bandwidth, and co-location constraints. They do so for architectures that utilize circuit-switched (rather than packet-switched) interprocessor communication and optimize latency and throughput in addition to load-balancing. Finally, these mapping algorithms make use of knowledge of the local scheduling discipline to accommodate real-time scheduling constraints. Our focus is on unstructured parallel programs that fall into one of two classes: (i) the class of computations characteristic of control applications in a real-time environment where tasks execute concurrently, periodically exchanging information, and (ii) pipelined computation graphs found in sensor data processing applications. The algorithms are implemented in a set of tools that operate with commercial CASE tools at one end, and present an interface to multiprocessor simulators at the other end. Collectively, the algorithms form a significant component of an interactive design environment for the development and mapping of real-time embedded parallel programs. The paper describes the algorithms, the encapsulating toolset, and presents an example of their application to an existing embedded application—an Autonomous Underwater Vehicle application.     

TAPER: query-aware,partition-enhancement for large,heterogenous graphs

Graph partitioning has long been seen as a viable approach to addressing Graph DBMS scalability. A partitioning, however, may introduce extra query processing latency unless it is sensitive to a specific query workload, and optimised to minimise inter-partition traversals for that workload. Additionally, it should also be possible to incrementally adjust the partitioning in reaction to changes in the graph topology, the query workload, or both. Because of their complexity, current partitioning algorithms fall short of one or both of these requirements, as they are designed for offline use and as one-off operations. The TAPER system aims to address both requirements, whilst leveraging existing partitioning algorithms. TAPER takes any given initial partitioning as a starting point, and iteratively adjusts it by swapping chosen vertices across partitions, heuristically reducing the probability of inter-partition traversals for a given path queries workload. Iterations are inexpensive thanks to time and space optimisations in the underlying support data structures. We evaluate TAPER on two different large test graphs and over realistic query workloads. Our results indicate that, given a hash-based partitioning, TAPER reduces the number of inter-partition traversals by \(\sim \)80%; given an unweighted Metis partitioning, by \(\sim \)30%. These reductions are achieved within eight iterations and with the additional advantage of being workload-aware and usable online.     

动态图划分算法研究综述

图划分是大规模分布式图处理的首要工作,对图应用的存储、查询、处理和挖掘起基础支撑作用.随着图数据规模的不断扩大,真实世界中的图表现出动态性.如何对动态图进行划分,已成为目前图划分研究的热点问题.从不同动态图划分算法的关注点和特点出发,系统性地介绍当前可用于解决动态图划分问题的各类算法,包括流式图划分算法、增量式图划分算法和图重划分算法.首先介绍图划分的3种不同的划分策略及问题定义、图的两种不同的动态性来源以及动态图划分问题;然后介绍3种不同的流式图划分算法,包括基于Hash的划分算法、基于邻居分布的划分算法以及基于流的优化划分算法;其次介绍单元素增量式划分和批量增量式划分这两种不同的增量式图划分算法;再次,分别介绍针对图结构动态的重划分算法和针对图计算动态的重划分算法;最后,在对已有方法分析和比较的基础上,总结目前动态图划分面临的主要挑战,提出相应的研究问题.     

Partitioned linear estimation algorithms: Discrete case

Using the "partitioning" approach to estimation, fundamentally new, robust, computationally effective and fast filtering and smoothing algorithms have been obtained. The new algorithms are given in explicit expressions of a partitioned nature in terms of decoupled forward filters. The "patitioned" algorithms are especially advantageous both from a computational as well as an analysis standpoint. They are the natural framework for studying observability, controllability, unbiasedness, and especially in deriving robust, fast, and effective numerical algorithms for Riccati equations.     

Exploiting early sorting and early partitioning for decision support query processing

Decision support queries typically involve several joins, a grouping with aggregation, and/or sorting of the result tuples. We propose two new classes of query evaluation algorithms that can be used to speed up the execution of such queries. The algorithms are based on (1) early sorting and (2) early partitioning– or a combination of both. The idea is to push the sorting and/or the partitioning to the leaves, i.e., the base relations, of the query evaluation plans (QEPs) and thereby avoid sorting or partitioning large intermediate results generated by the joins. Both early sorting and early partitioning are used in combination with hash-based algorithms for evaluating the join(s) and the grouping. To enable early sorting, the sort order generated at an early stage of the QEP is retained through an arbitrary number of so-called order-preserving hash joins. To make early partitioning applicable to a large class of decision support queries, we generalize the so-called hash teams proposed by Graefe et al. [GBC98]. Hash teams allow to perform several hash-based operations (join and grouping) on the same attribute in one pass without repartitioning intermediate results. Our generalization consists of indirectly partitioning the input data. Indirect partitioning means partitioning the input data on an attribute that is not directly needed for the next hash-based operation, and it involves the construction of bitmaps to approximate the partitioning for the attribute that is needed in the next hash-based operation. Our performance experiments show that such QEPs based on early sorting, early partitioning, or both in combination perform significantly better than conventional strategies for many common classes of decision support queries. Received April 4, 2000 / Accepted June 23, 2000     

Reusable components for partitioning clustering algorithms

Clustering algorithms are well-established and widely used for solving data-mining tasks. Every clustering algorithm is composed of several solutions for specific sub-problems in the clustering process. These solutions are linked together in a clustering algorithm, and they define the process and the structure of the algorithm. Frequently, many of these solutions occur in more than one clustering algorithm. Mostly, new clustering algorithms include frequently occurring solutions to typical sub-problems from clustering, as well as from other machine-learning algorithms. The problem is that these solutions are usually integrated in their algorithms, and that original algorithms are not designed to share solutions to sub-problems outside the original algorithm easily. We propose a way of designing cluster algorithms and to improve existing ones, based on reusable components. Reusable components are well-documented, frequently occurring solutions to specific sub-problems in a specific area. Thus we identify reusable components, first, as solutions to characteristic sub-problems in partitioning cluster algorithms, and, further, identify a generic structure for the design of partitioning cluster algorithms. We analyze some partitioning algorithms (K-means, X-means, MPCK-means, and Kohonen SOM), and identify reusable components in them. We give examples of how new cluster algorithms can be designed based on them.