（计算机应用技术专业论文）基于多核的并行软件工程的cdt模型的研究.pdf

摘要 摘要 随着计算机技术的不断发展，并行计算作为一种旨在降低运算时间、增加 问题求解规模、提高求解精度的方法，在科学以及工程应用的计算模拟、商业 应用的数据挖掘及事务处理等许多领域，已经产生了巨大的作用和影响力。近 几年来随着多核的逐渐普及，基于多核的并行计算的研究逐渐成为新的研究热 点。 。 范畴数据类型( c d t ) 模型是以范畴理论为基础，以数据类型的构造为目 的的形式化描述模型。c d t 模型具有非常严格的数学基础，并在软件工程中的 函数式程序设计与并行计算得到了一系列的应用，已经取得了不少的研究成果。 虽然c d t 模型的理论工作方面已取得了很多成果，c d t 构造的原理已经 有了较为完善的理论系统，但是将c d t 模型的理论与实际应用相结合，c d t 构造的原理与应用还有许多的问题值得探讨与研究。本文将c d t 模型创造性的 应用于多核平台之上，对c d t 理论的进行进一步的验证分析。 本文在研究国内外相关文献的基础上，从范畴数据类型的当前研究背景出 发，首先介绍了c d t 模型构造及基本原理等基础知识；详细研究了c d t 模型 最基本最重要的操作同态；以最有代表性的数据结构为例，给出了几种常见的 基础同态，并且进一步探讨了这些基础同态操作之间的关系；同时利用同构多 核平台，结合当前众多计算机硬件和软件厂商共同制定认可的指导多线程、共 享内存并行的应用程序编程接口刈p e 心佃技术，在p c 端实现了链表结构 的c d t 模型，并且对在单核平台与多核平台上同态操作的时间对比实验，进一 步证明了c d t 模型在并行计算领域的可行性。 关键词范畴数据类型；c d t 并行计算；多核；o p e n m p a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , p a r a l l e lc o m p u t a t i o nh a sb e e na m e t h o dw h i c hc a ns o l v ed e c r e a s i n gc o m p u t a t i o nt i m ep r o b l e m ，i n c r e a s i n gs o l u t i o n d i m e n s i o np r o b l e m ，a n de n h a n c i n gs o l u t i o na c c u r a c y p a r a l l e lc o m p u t a t i o nh a s g e n e r a t e dg r e a te f f e c ta n df u n c t i o ni nc o m p u t a t i o n a ls i m u l a t i o na b o u ts c i e n t i f i c a p p l i c a t i o na n de n g i n e e r i n ga p p l i c a t i o nd o m a i n ，d a t am i n i n ga n dt r a n s a c t i o nd o m a i n ， e t c w i t ht h ep o p u l a r i z a t i o no fm u l t i p r o c e s s o lt h er e s e a r c ho np a r a l l e lc o m p u t a t i o n w h i c hb a s e do nm u l t i p r o c e s s o rh a sb e e nn e wr e s e a r c hh o t s p o t c d t ( c a t e g o r i c a ld a t at y p e ) m o d e li sad a t at y p et h a tb a s e do nc a t e g o r i c a l t h e o r y , i ti saf o r m a ld e s c r i p t i v el a n g u a g ew h o s ea i mi sc o n s t r u c t i o no fd a t at y p e c d tm o d e li sb a s e do ns t r i c tm a t h e m a t i c st h e o r ya n db e e na p p l i e di nf u n c t i o n a l p r o g r a m m i n ga n dp a r a l l e lc o m p u t i n go fs o f t w a r ee n g i n e e r i n g i th a sg a i n e dl o t so f g r e a tp r o d u c t i o na b o u tc o m p u t e rs c i e n c e a l t h o u g ht h eg r e a tp r o d u c t i o na b o u tc d t m o d e lh a sb e e ng e ta n dt h et h e o r yo f c d tm o d e lh a sp e r f e c tt h e o r e t i cs y s t e m b yt h er e s e a r c ha n da n a l y s i so fc d t m o d e li nt h e o r e t i ca n dp r a c t i c a la p p l i c a t i o n ，al o to fp r o b l e m si sw o r t ho fa p p r o a c h t h i st h e s i sw i l lg i v ec d tm o d e la p p l i e do nm u l t i - p r o c e s s o rp l a t f o r ma n dg i v e f u r t h e rv a l i d a t i o na n da n a l y s i so nc d t t h e o r y b a s e do nt h ed o m e s t i ca n di n t e m a t i o n a lr e f e r e n c e s ，t h i st h e s i ss t a r t st h e r e s e a r c hf r o mt h eb a c k g r o u n do fc a t e g o r i c a ld a t at y p ep r e s e n tr e s e a r c h f i r s t l y , w e i n t r o d u c et h em o s tf u n d a m e n t a la n di m p o r t a n tk n o w l e d g eo fb a s a lc a t a m o r p h i s m s ； s e c o n d l y , w er e s e a r c ht h eb a s i ca n ds i g n i f i c a n tp a r to ft h ec a t a m o r p h i s m si nd e t a i l ， t a k i n gt h em o s tr e p r e s e n t a t i v ed a t as t r u c t u r ef o re x a m p l e ，a n df u r t h e rd i s c u s st h e r e l a t i o n s a m o n g t h e s e c a t a m o r p h i s m s ；a tt h e e n dw eu t i l i z e i s o m o r p h i c m u l t i p r o c e s s o r , c o m b i n i n go p e n m pw h i c hi s aa p i ( a p p l i c a t i o np r o g r a m m i n g i n t e r f a c e ) e s t a b l i s h e db yan u m b e ro fc o m p u t e rs o f t w a r ea n dh a r d w a r em a n u f a c t u r e r t h a tc a ni n s t r u c tm u l t i t h r e a d i n ga n ds h a r e dm e m o r yp a r a l l e l i s m w ec o n s t r u c tc d t m o d e lo fl i s t ，a n dc o m p a r et h ep e r f o r m a n c eo fc a t a m o r p h i s m se x e c u t et i m eo n d o u b l e - p r o c e s s o r sa n ds i n g l ep r o c e s s o r s ，f u r t h e rt e s t i f yt h ef e a s i b i l i t yc d tm o d e li n p a r a l l e lc o m p u t a t i o nd o m a i n k e y w o r d sc d t ；p a r a l l e lc o m p u t a t i o n ；m u l t i p r o c e s s o r ；o p e n m p i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特另t l d n 以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 繇华吼弓幽 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：婢导师签名- 毕 第l 章绪论 ii i 1 1 研究背景 第1 章绪论 范畴论产生于二十世纪四十年代对于同调代数的研究。经过几十年的迅速 发展，范畴论已经发展成为一门具有广泛应用的新理论。在现代数学研究中， 范畴论为多样的数学分支以及各个分支之间多样化的联系提供了一种统一的符 号语言，目前已经在代数学、拓扑学、几何学等领域有着深刻的应用。在逻辑 学中，以范畴论为基础的t o p o s 理论正在发展成为现代数学全新的统一的基础 【l 】 o 范畴论主要研究的是对某些特定的数学对象和映射的概括和抽象【2 儿3 1 。传 统的方法是要集中精力于研究数学对象本身，范畴论的作法则是要强调数学对 象间保持对象结构不变的态射【4 j 。 范畴理论还是一门在计算机学科中具有广泛应用的数学学科，范畴论对于 区别数学结构、理论、语言和形式系统的联系，特别是对于理解各种规范、设 计、正确性证明和程序设计语言之间的联系方面是很有益处的。c d t ( 范畴数 据类型) 模型正是以范畴理论为基础发展起来的理论科学，因此也在计算机科 学的各个领域发挥着极大的作用。由于软件工程形式化方法的许多概念在范畴 论中能够得到更清晰的解释【5 j ，因而范畴论被视为计算机科学中强有力的数学 工具，广泛应用在函数式语言设计、多态类型系统等语义模型领域 6 , 7 1 ，并行理 论的范畴论【8 】、软件工程中软件体系重构等应用【9 , 1 0 , 1 1 , 1 2 ，因此范畴论是一个对 计算机理论与实际应用中都非常有意义的研究领域。 近几年来，并行处理逐渐成为解决人类重大挑战问题的关键技术。计算机程 序设计本身就是一个相当复杂和困难的研究，至于并行程序设计将这一研究进一 步的复杂化。范畴数据类型提供了一个强有力的方式去构造与机器结构无关的并 行处理程序。这种并行程序带有一个程序变换系统和一个完备性保证机制，这就 使范畴论从理论上对并行设计提供了支持。因此，c d t 是一个适合于并行软件开 发的且建立在良好数学基础之上的并行计算模型，它也是一个尤其适合并行处理 的抽象数据结构【4 j 。 而当前并行计算中存在的最大问题就是并行计算的硬件和软件不匹配问题。 究其原因就是由于软件的发展跟不上硬件的快速升级。为了使并行计算的软件 能够独立于硬件，不受硬件发展的影响而不断地更新，希望构造一个抽象的并 行机模型，软件可以在此抽象的并行机模型上运行，这样当硬件发生变化时， 北京工业大学工学硕士学位论文 并不需要改动软件就可以直接运行。这样的抽象并行机模型当然要提供一个基 本上与硬件无关的运行环境。自i n t e l 公司在2 0 0 5 年公布第一款双核处理器， 目前多核处理器大有取代传统单核c p u 之势。并行计算机已经不再是大型复杂 计算机的代名词，p c 机已正式进入并行计算时代。把c d t 模型应用在多核的 基础之上，这不仅是对软件工程的并行理论的充实与发展，更是对多核应用提 供了新的思路。 并行计算进入日常开发的难度就在于编程模型，太复杂的东西会被人所抛弃， 构建c d t 模型，使之与多核技术相结合，形成相对简单的编程模型，这不仅体现 了科研价值，在应用领域也有巨大的潜力可挖掘。 以范畴论为基础的a d t ( 抽象数据类型) 的研究对计算机软件的发展起到了 很大的推动作用，并直接导致了软件开发中面向对象技术的产生【l l 】 1 2 】。而c d t 是对a d t 的进一步推广。为了建立新的a d t 类型，就必须选择这种类型对象上 的操作集合，由于不存在一个选择操作集合的结构性方法使得所有有用的函数都 能表示出来；同时也没有一个构造方程集合的通用方法来保证，因此a d t 存在着 其本身固有的缺陷，从而使得人们去寻找某种解决办法，这就导致了c d t 的出现。 c d t 的实现只需通过与数据类型相关的构造器来实现，而无须考虑那些难以保证 其完备性的操作与方程，并且c d t 模型都是通过构造因子通过递归调用的方法实 现数据类型的构造，这个递归的过程是完全独立的，可以并行的执行。这就大大 简化了数据类型实现上的困难，所有关于数据类型的操作都是通过c d t 同态映射 操作来实现【4 】【1 3 】【1 4 】【1 5 】【1 6 】 17 1 。 因此本文主要对c d t 模型的基本理论中基础同态方面进行了深入的研究，在 此基础上，将c d t 模型在多核平台上构建了链表的c d t 模型，并对c d t 模型在多 核平台上表现给出了性能分析。 1 2 国内外研究现状及待解决问题 1 2 1c d t 模型 c d t 是对a d t 的进一步推广，具备并行操作的c d t 是完全可以应用在并 行计算领域的。建立在范畴理论的基础之上的c d t 是有足够深的理论基础来满 足软件开发的要求【8 j 。 a d t 类型，是由一组选择这种类型对象上的操作集合来定义的。为了建立 一个新的数据类型，必然存在一组选择对象类型的操作。这些操作可以分为三 类：构造器( c o n s t r u c t o r s ) ，用来建立新的类型对象；析构器( d e s t r u c t o r s ) ，用 第1 章绪论 曼鼍皇i ：| i i e i oi i i 皇曼 来删除新的类型对象中没用的部分：以及其它操作与函数。可是由于没有一个 结构化的方式来保证所有有用的操作都已经被挑选出来；同时，也没有一个通 用方法来确保这个方程集合满足：该集合包含描述类型的所有所需方程，并且 不存在多余的方程。因此操作集合中的错误是定义a d t 最常见的错误。c d t 构造方式的出现避免由抽象数据类型的先天不足带来的缺陷。c d t 的实现仅仅 依赖于选择基础类型的构造器来实现，而无须考虑那些难以保证其完备性的操 作与方程，所有关于数据类型的操作都是由c d t 同态操作来实现。这显然会遗 漏一些操作与方程，但在某些时候只需对整个数据类型的某些与构造过程同态 的这些操作进行考虑时是十分简洁并有效的处理，因此可以认为c d t 是a d t 的一种扩充与简化【l 引。 用范畴论的思想来研究数据类型来研究数据类型是比较晚才出现。范畴数 据类型( c d t ) 是h a g i n o 在它的博士论文中首先提出来的，同时h a g i n o 还给出 了c d t 的类型构造器，扩充了抽象数据类型( a d t ) 。之后又被w a i t e r s 、m a l c o l m 和c o c k e t 等人进一步发展。在相关工作中1 7 1 1 9 1 1 2 0 】【2 l 】，数据类型集成是由g a r d i n e r 开始的。m a l c o l m 的工作使得并行机制更加清楚。基于m a l c o l m 的思路， s k i l l i c o m 等人弱化了c d t 对范畴理论背景基础的要求。 以上是国外计算机工作者对各种数据类型所做的c d t 构造，这也是c d t 研究的一个重要方向，一种模型及是否具有强大的生命力往往取决于它的适应 范围和适应的好坏。因此，讨论c d t 的各种数据类型的构造就具有极大的理论 与现实意义。相比之下，国内对c d t 研究未能积极的开展，主要是由于c d t 离实际的并行计算应用还存在一定的差距 2 2 】【2 3 】【2 4 】【2 5 】。 目前计算机工作者对c d t 的研究主要集中在不同数据类型的c d t 构造、 并行算法的开发、基于c d t 变换的并行算法的代价估计等几个方面。在c d t 的基本理论及各种数据类型的构造方面已经取得了很好的成果，但是在将该理 论应用于实践方面做还很有很多工作需要来研究。 1 2 2 多核处理器 1 9 6 5 年，戈登摩尔( g o r d o nm o o r e ) 发现这样一条规律：半导体厂商能 够集成在芯片中的晶体管数量大约每1 到2 年就可以翻一番，即众所周知的摩 尔定律。在过去的四十年里，摩尔定律一直引导着计算机设计人员的思维和计 算机产业的发展。但是，单纯提高单核芯片的速度会产生大量的热量而无法提 高性能 2 6 1 。 于是“单个芯片多个核心”的多核处理器应运而生，即在单个处理器芯片上实现 # r i 大学i 学顿学位论文 两个或者更多的“执行核”，这些执行核都是相互独立的处理器，可以并行的执 行程序代码，在开发指令级并行性的同时，开发线程级的并行性，从而极大地 提高了处理器的性能。它们都具有自己的执行集合以及体系结构资源。下图给 出了不同结构配置核体系结构： 图1 - 1 单核处理器 f i 9 1 - 1s i n g l e c o m s s o t 面_ 、 图1 - 2 共享系统总线的取核处理器 围 - 3 共享l l c 和前端总线的双棱处理 器 f i g1 2 d o u b l e p r o c e s s o r 第1 章绪论 s h a r e ds y s t e mb u s s h a r e dl l ca n ds y s t e mb u s 多核处理器相较普通处理器主要具有显著的优势，片上多核处理器的结构 相对简单，更易获得高的主频；可以直接使用现有的处理器内核，因此开发周 期与成本相对较低；并且由于多个处理器集成在一块芯片上，且共享内存，微 处理器之间的通信延迟会明显降低，这就降低了多线程结构的重要问题一通信 延迟所带来的影响，有利于提高系统的整体性能；通过动态调节电压频率、负 载优化分布等，可有效降低c m p 功耗；微处理器厂商一般采用现有的成熟单 核处理器作为处理器核心，从而可缩短设计和验证周期，节省研发成本。 片上多核处理器不仅得到了学术界的广泛关注和深入研究，也得到了i b m 、 i n t e l 、a m d 、s u n 、h p 等大公司的认可，都已经推出了多核处理器，未来几年 处理器的发展趋势，片上多核处理器必将占据了主流的位置，成为进一步提高 微处理器性能的有效途径，因此针对这种结构的研究是非常必要和有意义的。 1 3 本论文的研究内容 本研究课题来源于北京市自然科学基金北京市自然科学基金资助项目 软件工程形式化的范畴论模型( n o 4 0 7 2 0 0 8 ) 。 本文在研究国内外相关文献的基础上，基于c d t 模型构造及基本原理等基 础知识以及c d t 模型最基本最重要的操作同态，以一个数据类型为例，在多核 平台上构造了这个数据类型的c d t 模型，并且对其性能进行了仿真实验，进一 步证明了c d t 模型适用于多核并行处理的可行性。具体研究内容如下： ( 1 ) 从范畴数据类型的当前研究背景出发，首先介绍了c d t 模型构造及基本 原理等基础知识，并且对这些基础知识进行了简化改进。 ( 2 ) 对c d t 模型中最基本最重要的操作同态进行了深入研究，进一步探讨了 c d t 模型中几种常见的基础同态之间的关系，并且对这些关系给出了证 明。 ( 3 ) 同时利用同构多核平台，根据c d t 模型构造原理，结合当前众多计算机 硬件和软件厂商共同制定认可的指导多线程、共享内存并行的应用程序 编程接口o p e n m p 技术，在p c 端实现了链表结构的c d t 模型，并 且对在单核平台与多核平台上同态操作的时间对比实验，进一步证明了 c d t 模型在并行计算领域的可行性。 北京工业大学工学硕士学位论文 1 4 论文的组织结构 本文的章节安排如下： 第一章绪论部分，介绍论文的主要研究对象，课题的背景和国内外研究现 状以及论文的主要研究内容和论文的结构。 第二章首先从数学概念上介绍了范畴，接下来介绍构造范畴数据类型需 要的基本概念，之后进一步对构造的基本原理作了深入的探讨，进一步研究 了c d t 变换及c d t 的因子分解定理。 第三章首先介绍了并行机的f l y r m 分类，基于f l y r m 分类法的不同类别 详细介绍了传统的几种并行计算模型。最后提出c d t 模型并阐述其所具有其 他模型没有的优势。 第四章继续对c d t 理论进行研究，以表结构的c d t 模型为例，进一步 研究基于c d t 模型之下的基础同态之间的关系。 第五章在前几章的理论基础之上，采用第二章的中介绍到的s k i l l i c o m 的 方法，在p c 多核平台上建立了一个链表结构的c d t 模型并分析c d t 模型 在p c 平台上的性能表现。 结论部分对整篇论文进行总结，并展望下一步工作。 第2 章c d t 模型相关理论 第2 章c d t 模型相关理论 本章首先从数学概念上介绍了范畴，接下来介绍构造范畴数据类型需要的 基本概念，之后进一步对构造的基本原理作了深入的探讨，进一步研究了c d t 变换及c d t 的因子分解定理。 2 1 范畴论中的基本概念 2 1 1 范畴 现代数学中许多数学领域的研究都可以概括为对特定的数学对象以及这些 对象之间的映射的研究。范畴的概念正是对这些特定的数学对象和映射的概括 和抽象【1 6 】。 定义2 1 一个范畴( c a t e g o r y ) c 是由 1 】： ( 1 ) 一族对象( o b j e c t ) 记作o b c ( 2 ) 任意一对对象a ，b ，对应一个集合c ( a ，b ) ，其元素称为态射( m o r p h i s m ) 使得当a a 。或者b b 时，c ( a ，b ) 与c ( a ，b ) 不相交 组成，并满足下面条件： ( a ) 复合律( c o m p o s i t i o nl a w ) ：若a jb ，c o b c ，f c ( a ，b ) ，g c ( b ，o ， 则存在唯一的g f c ( a ，o ，称为f 与g 的复合。 ( b ) 结合律( a s s o c i a t i v i t y ) ：若a jb ，c ，d o b c ，f c ( a ，b ) ，g c ( b ，c ) ， h c ( c ，d ) ，则有 h ( g o = ( h 曲f ( c ) 单位态射( i d e n t i t ym o r p h i s m ) ：每一个对象a ，存在一个态射1 a c ( a ，a ) 使得对任意的f c ( a ，b ) 及g c ( c ，a ) 有： f l a = f i a g = g c 态射的全体记作m o r c 。 2 1 2 函子 在范畴论中，不仅仅关注对象，而且更关注对象之间的对应关系，即范畴 之间的映射函子。 定义2 2 设c 和d 都是范畴。一个函子( f u n c t o r ) ：f ：c _ d 由两个映射组成： o b c - o b d ：a - f ( a ) 北京工业大学工学硕士学位论文 m o r e - m o r d ：f - f ( 0 满f f ：d o m ( f ( 0 ) = f ( d o m ( f ) ，c o d ( f ( 0 ) = f ( c o d ( f ) ) ，f ( 1 a ) = i f ( a ) ，并且若 d o m ( g ) - - c o d ( f ) n f ( 9 0 = f ( 曲f ( f ) 任意范畴c 都存在一个到自身的单位函子1 c ：c _ c 使得在对象和态射上 的对应都是恒同的。 接下来我们简要地介绍c d t 构造的相关理论背景。 2 2c d t 构造 2 2 1 基础范畴 基础范畴c 是进行c d t 构造的基础，比一般范畴具有更加严格的要求【2 7 】。 定义2 3 基础范畴c 是由数据对象( a ，b ，) 和同态( g ，) 构成， 并满足如下条件： ( a ) 存在范畴c 上的积以及余积。 ( b ) c 中包含有初始对象0 以及终极对象1 。 基础范畴具有以下性质： ( 1 ) 自态射：i d a ：a a ( 2 ) 对任意态射f a b ，则有 f i d a = f i d b f = f ( 3 ) 设两个态射f a b ，g ：b - c 存在，那么存在一个态射( g f ) ( g f ) ：a 一c ( 4 ) 初始对象0 ：存在唯一的态射从初始对象0 到基础范畴中任意其他的对 象。 ( 5 ) 终止对象1 ：存在唯一的态射从基础范畴中任意其他的对象到终止对象 0 ( 6 ) 对于所有的配对对象a ，b ，存在复合对象a b ，对于复合对象axb ， 存在态射： p r o j a ：axb _a p r o j b ：axb - b ( 7 ) 对于所有的配对对象a ，b ，存在复合对象a + b ，对于复合对象a + b ， 存在态射： 第2 章c d t 模型相关理论 c o p r o j a ：a 一a + b c o p r o j b ：b 一a + b ( 8 ) 对基础范畴中任意态射f a _ b ，g ：b c j h ：c - d ，有 h ( g d = ( h g ) f 2 2 2 类型函子 定义2 4 自函子f ：c - c 就是将范畴c 的对象映射到c 的对象，将c 的态射 映射为c 的对象态射，并保持恒等态射及态射的合成： f ( f a - b ) = f f ：f a _ f b f ( f g ) = f f f g f - i da = i d f a 范畴c 中的特殊类型函子除了自函子同时还有多项式函子，由于多项式函 子存在不动点 4 】而这样的多项式类型函子存在着可逆函子。 定义2 5 所谓多项式函子就是：恒等函子是多项式函子，常数函子是多项 式函子，如果f , g 是多项式函子，则fxg ，f + g ，g f 也是多项式函子。恒等函 子定义为( a ，b 皆为范畴c 中的对象) ： i ：a - i ( a ) = a i ：( f a _ b ) _ i ( f a _ b ) = f a _ b 常数函子定义为：( a ，b 皆为范畴c 中对象，k 为常数) k ：a k ( a ) = k k ：( f a - b ) 一i d x ：x _ x 2 2 3t - 代数范畴( t - a l g e b r a s ) 定义2 6 设c 是一个范畴，t 是c 上的自函子，t - 代数就是函子f t a - a ，其 中a 是c 中的对象。 定义2 7t - 同态：给定类型函子t ：c c ，t - 代数f t a - a 和g ：t b b ，当 h ：a - b 满足h f = g t h 时，称h 为t - 同态。 h 有两层含义，一方面表示基础范畴对象的态射，另一方面表示t - 代数态 射，即f - g 。如图2 1 所示。 北京工业大学工学硕士学位论文 l 图2 1t 代数间的i 司态 f i g2 - 1h o m o m o 巾h i s mb e t w e e nt - a l g e b r a s 如此可以定义t - 代数范畴( 记为t - a l g e b r a s ) ，它的对象是t 代数，态射是t - 同态，如图2 1 。由此我们可知当a 是某种类型时，t - a l g e b r a s 事实上是一种能 够保持结构的类型范畴。 定义2 8 当同态( h o m o m o r p h i s m ) 存在逆同态的时候，我们叫这个同态 为同构同态( c a t a m o r p h i s m ) ，实际应用中，大部分要研究的同态都是这种同构 同态。 t - 同态与代数中映射在本质上是相同的，唯一的区别就是t 同态内容包括 范畴c 中的对象之间的同态，另一个则是态射的同态。 2 2 4c d t 的构造步骤 根据d bs k i l l i c o m 的观点，范畴数据类型的构造通常分为以下四步弘1 ： 1 ) 定义一个基本范畴c ，这个范畴c 由一些基础类型和函数组成。这些基 础类型被看作范畴理论中的c - 对象，这些函数被看作c 态射。 2 ) 定义一个类型函子( t y p ef u n c t o r ) t 。类型函子t 是c 上的一个自函子。 类型函子t 导出一个结构化的数据类型以及它的构造因子。由类型函子t 导出 的c d t 是一个c 对象a ，并且”是t 的c 对象的一个不动点。的构造因子则 是一个c 态射t ，而t 就是t 的c 态射的一个不动点。 3 ) 构造t 代数范畴( 记为t - a l g e b r a s ) ，t - a l g e b r a s 的对象就是我们构造的类 型以及代数关系，t - a l g e b r a s 的态射就是构造类型的同态。这个构造类型还是 t - a l g e b r a s 的初始对象。 4 ) 给出c d t 的一般规则，即实际应用中对数据类型的操作，通过c d t 的并行机制，对数据类型进行分解，并行化执行。 第2 章c d t 模型相关理论 2 3 常用数据类型的c d t 构造 2 3 1 表的c d t 构造 我们要创建的表是以某种基本类型a 为元素的，并且把构造好的表的类 型以a 木来标记。表的构造器如下【2 7 】【2 8 】： 口：1 - 】：a _ a + ：a + a _ a + 其中，第一个构造器口定义的是空序列；第二个构造器 】表示将数据类型 为a 的元素加入到一个表结构中；第三个构造器丰表示将任意两个表连接成 单一表。 此时，在基础范畴中定义一个自函予： t ：”一1 + a + a 。a + 由于此表结构的自函子t 是以基本类型a 来构造的，因此为了更加清晰的 表示此依赖关系，此后以t a 来表示t 。 根据范畴理论，此函子作为多项式函子具有不动点，设此不动点为a f i x ，显 然下式成立： t a ：a f t x - 1 + a + a f i x a f i x 由表的c d t 构造过程可知，a f i x 和t a f t x 之间的态射是同构态射，即a f i x 和 t a f t x 是同构关系。因此，存在一对同构映射： t = v v 牛：1 + a + a - t - 1 ：a 时1 + a + a 。( 其中v 表示不同构造器的合成) 当存在表的c d t 类型时， t - 代数就是由函子t 给出的数对( t x ，x ) 及射t x _ x 。有如下的t a 代数： f = v 】v 牛：t aa 。_ a 现在考虑这样的范畴，它的对象是t a - 代数，它的射是t a 代数同态。t 1 代数同态就是那些保持t a - 代数结构的映射。例如，设h 是从t a x - x 到 t a y - y 的t a 一代数同态，那么它必然由t a x - t a y 和x - y 两个射组成。我们 令0 【：t a x 一x 和p ：t a y _ y ，从而有下式成立： 北京工业大学工学硕士学位论文 f 一1 h a = b t h t h t a * t b f h a 木b 图2 - 2 初始i 司态的变换 f i g2 - 2h o m o m o r p h i s mf r o ma i li n i t i a lt - a l g e b r a 此范畴称为t a 一代数范畴，这个范畴中至少包含对象t a 代数，而且对象t a 一 代数是这个范畴中的初始对象。 由此可见h 可以通过一个递归调用来实现。其中映射f 1 是要构造的数据类 型构造器的逆，它实际是一个模式匹配器，即对构造过程的一个匹配过程：映 射t h 则是一个递归计算过程，因为n 1 可以继续不断地分解为其子过程，这个 过程往往存在着潜在的并行性，这就是c d t 在并行领域得到应用的一个重要原 因；映射g 则是一个合成递归运算结果的过程，可见它其实就是一个构造的过 程。 已知t a 一代数范畴的初始对象就是t a - 代数和在它上的射t ，而且此t 还有逆 1 ；- 1 。 对于任意的t a 一代数包含三部分，即类型p ，类型t a p 以及态射： 1 + a + p p p 。 此时，运用表的c d ta + ，可以得到图2 2 表的c d t 变换。从图2 2 可以 得到间接计算h 的方法，即从左到顶再到右的箭头的合成。 故有： h = ( 口v 【】v 牛) t h t - 1 成立。 由此我们可以说凡是与t a 代数同态的对象均可由此c d t 的代数变换得 到。这是c d t 具有广泛应用的基础。 注：由于( t a a * ，a ) 是t 1 代数范畴中的初始对象，因此从c d t 出发到其 它的对象总能使得图2 2 成立。 第2 章c d t 模型相关理论 ! i 一。； i i i 曼! 曼蔓曼曼鼍曼曼曼曼 2 3 2 二叉树的c d t 构造 以树为数据类型的范畴构造是由g i b b o n s 的论文中提出的【1 5 】，在这里我们 仍然应用他的定义。 二叉树的数据类型可以由下列构造器实现【3 0 】： 6 ：a _ a t 九：a t axa t a t 其中6 是由给定类型a 的任意值来构造二叉树的一个叶子，九是将2 个树 和一个a 值来构造1 个更大的树。 基本范畴c 对于完全二叉树数据类型，它的范畴c 的对象就是按下述方式构成 的二叉树：每个节点包含有集合a 的1 个值，每个节点要么有2 个后代，要么没 有后代。该范畴的每个对象是1 个类型( 即1 个集合) 。 类型函子范畴c 是非常丰富的，包含其中的对象都是许许多多的c d t ，而包含 其中的映射也都是可用于这些c d t 的许许多多的函数。然而，c 也包含着一些不是 c d t 的对象，因为这些对象缺乏c d t 所要求的结构特性。同时也可能引入一些并 不保持c d t 结构的函数。可以用类型函子过滤掉范畴c 中所不希望的那部分。 t a - 代数一个t a 代数是一个映射f t a - a ，表示a 的一个具体代数结构。对于 数据类型a ，他的t a 代数可以定义为一个映射 f - a + bxaxb 其中f = f lr e 2 ( v 表示函数的合成) ，f 1 ：a - b ，f 2 ：bxa b - b 。 递归框架二叉树的递归调用时很明显的，当对一个复杂二叉树进行同态操作时， 首先记录根节点信息，如左右结点仍为二叉树时，继续重复之前的操作。由于对 左右子树的操作是相互独立的，所以这两个过程是可以并行处理的。并行性的总 的程度取决于应用该函数的具体树的大小和结构。 北京工业大学工学硕士学位论文 2 3 3c d t 构造的性质 图2 3 二叉树的同态映射 f i g2 - 3t r e ec a t e m o r p h i s m s 性质2 1c d t 变换与t 同态的合成仍是一个c d t 变换。 证明：设( g ) 是满足上面所说的一个c d t 变换，即有：h = g t h f _ 1 ，并设存 在一个与g ：t b _ b 同态的t - 代数是l ：t c - c ，此时有：k - g = 1 t k ( 根据 t 同态的定义) ，如图2 4 所示可得： t ht k t a 木t b t c f 一1 f 卜 胁l b l c a ，i c = r 图2 4c d t 变换与t 同态的合成 f i g2 - 4c d th o m o m o r p h i s ma n dc a t a m o r p h i s m s k h = k g t h f 一1 = 1 t k t h f - 1 = l t ( k h ) f 一1 这说明k h 是一个c d t 变换，即从到c 存在一个c d t 变换。证毕。 i。，。，。llll。 第2 章c d t 模型相关理论 性质2 2 如果t - 代数范畴中存在有对象到初始对象的t 同态，那么这个对象也 是初始对象。 证明：由于初始对象到t - 代数范畴的任意对象都存在有唯一的态射，也就是说 存在态射h 使得图2 1 成立，又根据假设t - 代数范畴中存在有对象到初始对象 的t 同态，可以得到如下结论，t - 代数范畴中的该对象到到t - 代数范畴的任意 对象都存在有t 同态，因此该对象就是t - 代数范畴中的初始对象。不仅如此， 根据初始对象的唯一性，该对象故初始对象还是同构的。证毕。 、 又上面的构造过程可知，构造因子的作用就是为了形成一个t - 代数范畴， 然后产生c d t 变换，而c d t 的最终应用都是根据c d t 变换的作用达到的。由 此可以这样来看c d t 构造的实质，如果把基础范畴理解为一个包含了全部数据 类型及其它许多对象的范畴，为了得到某种数据类型的c d t ，其实就是从这个 庞大的基础范畴中找到对应该数据类型的那些对象，通过给出构造因子的目的 就是对基础范畴进行挑选的过程，就如同给出一个函子将基础范畴变换到另一 个范畴的过程。 2 3 4c d t 的因式分解定理 为了进一步探索c d t 适合并行的秘密，对于数据的操作都是通过c d t 变换来实现的。这些变换反映了使用c d t 编程的本质。下面将给出c d t 变 换的因子分解定理【2 i 】【3 1 】。 构造函子t 依赖于基本类型a 的选择，所以采用双函子的方式来表示这种 关系，即： t a * = a r e a * ：a + 一a + f ( a + ) 定义2 9对于给定的一个函子g ：a 甲a a ，定义c d t 的归约为：a 木_ a ，即 为( 朗) 。 如图2 5 。 北京工业大学工学硕士学位论文 f i 图2 5c d t 规约 f i g2 5c d t r e d u c t i o n 定理2 1如果存在函子g ：a w a a 及f a - b ，那么对任意的h ：a w b 一b 都 存在如下的因子分解定理： ( h 】) = f g 证明：由假设可知存在函子g ：a 甲a a ，故g 是t - a l g 的对象，因而存在唯一 的a - a 态射，即g ：a - a ，又根据h ：a w b - b ，可得存在唯一的态射 h ：a 宰_ b ，记为( 朗) 。 现在问题转化为证明f g 也是a 木一b 的态射，由于唯一性结论即得。 t g f t = t g a w g = h a 甲f a w g = h t f t g | = h t ( f g ) 图2 - 6 c d t 的因式分解 f i g2 - 6c d t f a c t o r i z a t i o n 1 6 第2 章c d t 模型相关理论 由此可知f g 是- b 的t - n 态，即是t - a l g 的a - b 的态射。 证毕。 该定理说明了对于c d t 的程序规则其实在满足一定的条件下都可以分解 为关于c d t 的一个映射与归约的合成，这样一来，以后对c d t 变换的研究 就可以运用分解的方式进行，从而大大减少分析的复杂性。 2 3 本章小结 本章首先从数