主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
容红波,汤志忠.基于路径分组与数据相关松弛的软件流水.软件学报,2001,12(4):544-555
基于路径分组与数据相关松弛的软件流水
Software Pipelining Based on Path Grouping and Data Dependence Relaxation
投稿时间:1999-11-15  修订日期:2000-01-25
DOI:
中文关键词:  指令级并行  软件流水  路径  概率  数据相关
英文关键词:instruction level parallelism  software pipelining  path  probability  data dependence
基金项目:国家自然科学基金资助项目(69773028)
作者单位
容红波 清华大学计算机科学与技术系北京 100084 
汤志忠 清华大学计算机科学与技术系北京 100084 
摘要点击次数: 2412
全文下载次数: 2692
中文摘要:
      软件流水是循环调度的重要方法.有分支循环的流水依然是个难题.现有算法可以分为4类:循环线性化、路径分离、整体调度和路径选择.它们都未能和谐地解决两个对立问题:转移时间最小化和最差约束问题.提出了基于路径分组和数据相关松弛的软件流水框架,试图无矛盾地解决上述问题.其主要思想是:(1)路径分组,即按照路径的执行概率和转移概率将路径分组,力求最小化转移时间;(2)数据相关松弛,力求避免最差约束,即当循环有多条路径时,有些相关在循环执行中并不一定有实例,理想的策略是仅当它有实例时才遵守.初步实验和定性分析表明,此
英文摘要:
      Software pipelining is an effective approach of loop scheduling. Pipelining of loops with conditional branches remains a challenge. Current algorithms are divided into four classes: loop linearizaton, path splitting, as-a-whole scheduling and path selecting. All of them fail to solve concurrently two conflicting problems: transfer time minimization and worst-case constraints. In this paper, a novel software pipelining framework is presented to do so. The key ideas are: (1) Path grouping, which splits paths into distinct groups based on their execution and transfer probability, so as to minimize transfer time; (2) Data dependence relaxation. Some data dependences may not have instances during execution when the loop has multiple paths. The ideal policy is to obey them only when they have instances. Thus the worst-case constraints are avoided. Preliminary experiments and qualitative analysis all suggest that the temporal benefit of the proposed approach is better than that of path splitting and as-a-whole scheduling.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利