基于图的分解与合并的静态事务调度算法  

A Static Transaction Scheduling Algorithm Based on the Decomposition and Composition of Graph

作　　者：幸冬梅[1,2] 

机构地区：[1]复旦大学计算机科学与工程系,上海200433 [2]南昌大学数学系

出　　处：《计算机研究与发展》2008年第z1期57-61,共5页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60496321)

摘　　要：在各种数据系统的处理中,总有一系列相对独立而相互关联的事务系列组成.如何合理地安排这样的事务的顺序,一直是数据系统优化中存在的问题.该问题的一般化形式是一个NP问题,可以归约为一个点、边均有权值的图上有多输入、多输出问题,寻找时间代价最小且使得点和边尽可能满足容量需求的最短路径.为此,考虑一种基于图的分解与合并的计算方法,利用一种新的算法,并从理论上分析其优良性.In the processing of all sorts of data systems, there exist a series of independent and relating transactions that compose these processing. It is always a optimal problem in data systems how these transactions are arranged. The normalized forms of them is NP-complete, which can be reduced to a source-sink pairs problem in a directed graph with both node-capacitated and edge-capacitated in order to find the shortest paths for the source-sink pairs and it takes less time in the meantime. In this paper an algorithm based on the decomposition and composition of graph is considered. Then the function of the algorithms is analyzed theoretically using a new kind of methods.

关 键 词：图分解 事务调度 v-separable 独立子图 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]