本文给出平行结构类问题及其求解系统的形式化描述,讨论了此类问题的分解与任务分布,并提出了一种IPD算法(Improved Problem Decomposition).该算法从规模上将问题分解为若干性质相同的任务,按就近原则将任务预分布到系统中各结点上,并...本文给出平行结构类问题及其求解系统的形式化描述,讨论了此类问题的分解与任务分布,并提出了一种IPD算法(Improved Problem Decomposition).该算法从规模上将问题分解为若干性质相同的任务,按就近原则将任务预分布到系统中各结点上,并通过启发式状态空间查找方法进行负载调整,使系统负载平衡.试验表明:IPD算法的分解分布结果负载平衡,系统潜在协作量小.展开更多
Existing global microcode compaction approaches have all assumed a target architecture that has microoperation conflicts and data dependencies as the two fundamental compaction constraints.However, new practical micro...Existing global microcode compaction approaches have all assumed a target architecture that has microoperation conflicts and data dependencies as the two fundamental compaction constraints.However, new practical micromachine features demand that the timing constraint be introduced into the traditional compaction model to guarantee compaction correctness.This paper starts by an analysis on the nature of timing constraints,then modifies the roles for microoperation motions,presents an algorithm,TST,based on Trace Scheduling,for global compaction under timing constraints,and finally shows results of experiments.展开更多
This paper uses timed Petri net to model and analyze the problem of instructionlevel loop scheduling with resource constraints, which has been proven to be an NP complete problem. First, we present a new timed Petri n...This paper uses timed Petri net to model and analyze the problem of instructionlevel loop scheduling with resource constraints, which has been proven to be an NP complete problem. First, we present a new timed Petri net model to integrate functional unit allocation, register allocation and spilling ilno a unified theoretical framework.Then we develop a state subgraph, called Register Allocation Solution Graph, which can effectively describe the major behavior of our new model. The maill property of this state subgraph is that the number of all its nodes is polynomial. Finally we present and prove that the optimum loop schedules can be found with polynomial computation complexity, for almost all practical loop prograrns. Our work lightens a new idea of finding the optimum loop schedules.展开更多
文摘本文给出平行结构类问题及其求解系统的形式化描述,讨论了此类问题的分解与任务分布,并提出了一种IPD算法(Improved Problem Decomposition).该算法从规模上将问题分解为若干性质相同的任务,按就近原则将任务预分布到系统中各结点上,并通过启发式状态空间查找方法进行负载调整,使系统负载平衡.试验表明:IPD算法的分解分布结果负载平衡,系统潜在协作量小.
文摘Existing global microcode compaction approaches have all assumed a target architecture that has microoperation conflicts and data dependencies as the two fundamental compaction constraints.However, new practical micromachine features demand that the timing constraint be introduced into the traditional compaction model to guarantee compaction correctness.This paper starts by an analysis on the nature of timing constraints,then modifies the roles for microoperation motions,presents an algorithm,TST,based on Trace Scheduling,for global compaction under timing constraints,and finally shows results of experiments.
文摘This paper uses timed Petri net to model and analyze the problem of instructionlevel loop scheduling with resource constraints, which has been proven to be an NP complete problem. First, we present a new timed Petri net model to integrate functional unit allocation, register allocation and spilling ilno a unified theoretical framework.Then we develop a state subgraph, called Register Allocation Solution Graph, which can effectively describe the major behavior of our new model. The maill property of this state subgraph is that the number of all its nodes is polynomial. Finally we present and prove that the optimum loop schedules can be found with polynomial computation complexity, for almost all practical loop prograrns. Our work lightens a new idea of finding the optimum loop schedules.
