Abstract: Many samples suit to use collective I/O in one zone, which needs to find a main process to do I/O of this zone. When more than one zone has the same main process, priority level need be assigned to each zone. This paper presented a new algorithm, multilevel maximal independent sets, to solve the above problem. Through analysis, this algorithm can realize the highest parallel degree of I/O and communication load is the least at the highest degree.

Key words: parallel i/o, connected graph, maximal independent sets, matrix

摘要： 针对划分计算空间到多个计算区域(zone)这类问题，采用基于计算区域组织I/O时，首先需选择计算区域的主进程；其次当某一进程是两个计算区域的主进程时需指定计算区域数据访问先后顺序。设计了多级极大独立集算法实现上述过程。该算法利用图论中的连通图以及极大独立集概念规定了每个计算区域进行数据访问的进程以及优先级。经样例分析，采用此种方法达到I/O并行度最高，并实现在并行度最高情况下通信量最小。

关键词: 并行I/O, 连通图, 极大独立集, 矩阵