并行语言并发程序细粒度链状数据结构维持分析翻译器.doc

并行语言论文：基于共享和形状标注的并行语言程序分析与变换【中文摘要】多核多处理新一代体系结构的迅猛发展,引发了软件开发方式上的巨变,为了能够充分地发挥体系结构上带来的优势,越来越需要并行编程和并发软件设计,但是,当前并行编程依然是件困难的事情。本课题组已经设计并实现了一种共享资源使用声明的并行程序语言SPC-II,它是基于共享内存模型的一种并行程序语言。与现有的并行语言不同,它最大特点在于为程序员提供一种访问控制的高级抽象,程序员不需要自己管理并发控制,而只需要声明所使用的共享资源,让编译器分析所使用的共享资源的保护区间,根据共享资源的保护区间插桩访问控制代码。本文在课题组的并行语言基础上,着重研究含有指针类型的链状数据结构访问控制,论文的主要研究内容有以下几个部分:1.一种链状数据结构自动细粒度加锁方法就细粒度并发访问链状数据结构提出一种自动方法,这些链状数据结构目前是单链表和双链表,通过分析SPC-II程序中的共享链状数据结构的形状信息来分析程序中共享数据单元的保护信息。2. SPC-II语言翻译器的实现在SUIF编译框架上,实现了一个并行语言SPC-II的编译器,该编译器实质上是一个源语言(SPC-II语言)到源语言(基于.【英文摘要】The rapid development of Multi-core or multi-processing architecture has brought drastic changes in the way of software development.In order to get the benefits of architecture, parallel programming and concurrent software design has become more and more important, but parallel programming is still a difficult task.Our group is studying a high-productivity parallel programming language base on shared resource useage declaration, which is based on shared memory model,it differents with the current existi.【关键词】并行语言 并发程序 细粒度 链状数据结构 维持分析 翻译器【英文关键词】parallel programming language concurrency program fine grained mutable data structure Concurrent access control holding analysis Translator【索购全文】联系Q1：138113721 Q2：139938848【目录】基于共享和形状标注的并行语言程序分析与变换摘要4-5ABSTRACT5-6第1章 绪论10-161.1 问题描述10-111.2 相关工作与研究现状11-141.2.1 常用的并发控制机制11-121.2.2 指针分析与形状分析12-131.2.3 锁分配算法13-141.3 研究内容14-151.4 论文组织15-16第2章 SPC-II语言16-342.1 具体语法16-222.1.1 共享性162.1.2 并行语句16-172.1.3 共享变量的维持语义17-192.1.4 形状声明19-202.1.5 变量20-212.1.6 程序实例21-222.2 抽象语法22-232.3 静态语义23-292.3.1 良型类型242.3.2 类型兼容24-252.3.3 良型类型上下文252.3.4 副作用25-262.3.5 共享效果262.3.6 良型表达式26-282.3.7 良型语句28-292.3.8 良型程序292.4 动态语义29-322.4.1 抽象机29-302.4.2 操作语义30-322.5 总结32-34第3章 一种链状数据结构细粒度加锁方法34-463.1 形状图34-363.1.1 定义34-353.1.2 内存抽象35-363.1.3 维持语义363.2 维持分析36-423.2.1 原子命令上的维持分析37-403.2.2 维持数据流分析40-413.2.3 实例分析41-423.3 访问控制代码生成42-433.3.1 细粒度锁语句插桩423.3.2 避免死锁42-433.4 实验结果和分析43-443.5 本章小结44-46第4章 SPC翻译器的实现46-664.1 Suif 编译框架46-514.1.1 中间表示46-484.1.2 控制流图48-514.2 SPC-II 设计与实现框架51-534.2.1 SPC 源程序524.2.2 程序分析524.2.3 目标代码52-534.3 形状图设计53-564.3.1 形状类型及其关系534.3.2 节点类534.3.3 边类和边集类53-544.3.4 形状图类544.3.5 形状图图形化输出54-564.4 维持分析数据流分析设计56-594.4.1 HoldingSetPiece564.4.2 HoldingSet56-574.4.3 NodeDS57-584.4.4 ThreadDS584.4.5 HoldingAnalysis58-594.5 细粒度锁代码生成59-614.5.1 锁分配策略59-604.5.2 结构体类型604.5.3 共享指针类型60-614.6 事务内存代码生成61-624.6.1 宏处理614.6.2 变量在存储语句中的变换614.6.3 变量在取值表达式中的变换61-624.6.4