（计算机应用技术专业论文）三值光计算机数据位资源的静态分配策略.pdf

上海大学硕士学位论文 摘要 光的空间巨并行性使得光学计算能拥有很高的数据宽度，依据最新研 究成果降值设计理谢2 1 ，三百位量级三值逻辑光学运算器模型已经研制 成功。因此，如何管理三值光计算机高数据宽度成为必须研究的课题。在 这个研究方向上，金翊教授描绘了一个管理光学计算机众多数据位数的思 想【l 】，但是没有给出具体的实现方案。2 0 0 7 年下半年我们开始对三值光计 算机高数据宽度管理技术进行全面研究。本文总结这个研究方向的第一步 研究成果给一个任务合理的分配数据位资源，其核心思想是给单任务 合理的分配数据位。该项工作将是今后进行三值光计算机多用户、多任务 条件下数据位资源管理策略研究的基础。 本课题受到国家自然科学基金项目( 6 0 4 7 3 0 0 8 ) 、上海市高等学校科学 技术发展基金项目( 0 4 a b 3 8 ) 、上海市重点学科建设项目( j 5 0 1 0 3 ) 和上海大 学博士点建设基金的支持。作者完成的工作主要有三个方面： 1 设计分组策略：包括对数据位资源进行静态分组；将数据位划分到 各个分组，从而确定各数据位的分组属性；设计与分配数据位相关的各种 表结构；以及建立分配数据位的工作流程。 2 编制分配管理系统软件：包括设计用户界面程序模块和编制软件； 设计分配数据位程序模块和编制软件。 3 软件测试：包括设计测试用例；设计实验过程；设计和实现测试结 果的输入输出方案；实施测试等工作。 测试结果验证了本文设计的管理策略和所编制软件的正确性。 关键词：三值光计算机；数据位管理；静态分配策略 v a b s t r a c t t e r n a r yo p t i c a lc o m p u t e rh a sal a r g en u m b e ro fd a t a b i t sb e c a u s eo fs p a t i a l t r e m e n d o u sp a r a l l e l i s mo f l i g h t a c c o r d i n gt ot h el a t e s tr e s e a r c hf i n d i n gn a m e d d e c r e a s e r a d i xd e s i g np r i n c i p l e ，am o d e lo ft r i - v a l u e dl o g i co p t i c a lo p e r a t i n g u n i t sp o s s e s s i n gh u n d r e d so f t e r n a r y - b i th a sb e e na c h i e v e ds u c c e s s f u l l y s oi t s n e c e s s a r yt os t u d yh o wt om a n a g et h ed a t a - b i tr e s o u r c e so ft e r n a r yo p t i c a l c o m p u t e rn o w i nt h i sf i e l d ，t h ep r o f e s s o rm rj i np u tf o r w a r do n es t r a t e g yt h a t h o wt om a n a g ea l a r g en u m b e ro fd a t a - b i t s ，b u th ed i d n tg i v ead e t a i l e dm e t h o d w es t a r t e dr e s e a r c h i n go nm a n a g e m e n t s t r a t e g yo fd a t a - b i t si nt h es e c o n dh a l f o f 2 0 0 7 t h ef i r s tr e s e a r c hf i n d i n gi sp u tf o r w a r di nt h i sp a p e r , a n dt h em a i ni d e ao f t h es t r a t e g yi st oa l l o c a t er e a s o n a b l yd a t a b i t st os i n g l et a s k t h i sj o bw i l lb et h e b a s i so fd a t a - b i tr e s o u r c e sm a n a g e m e n tp r a c t i c a ls y s t e mf o r m u l t i u s e ra n d m u l t i t a s k t h ew o r kw a ss u p p o r t e db yt h en a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o n o fc h i n a ( 6 0 4 7 3 0 0 8 ) ，t h es h a n g h a if o u n d a t i o nf o rd e v e l o p m e n to f s c i e n c ea n dt e c h n o l o g y ( 0 4 a b 3 8 ) ，s h a n g h a il e a d i n ga c a d e m i cd i s c i p l i n e p r o j e c t ( j 5 0 10 3 ) a n dt h ed o c t o r a t ef o u n d a t i o no fs h a n g h a iu n i v e r s i t y t h em a i nc o n t e n to ft h ep a p e ri n c l u d e sf o l l o w i n gt h r e e p a r t s ： f i r s t l y , t h ew r i t e ri sr e s p o n s i b l ef o rd e s i g n i n gt h eg r o u p i n gs t r a t e g y , i n c l u d i n gs t a t i cg r o u p i n gd a t a - b i t s ，d e s i g n a t i n gd a t a b i tr e s o u r c e si n t oe v e r y g r o u p ，s e r i n ga t t r i b u t ef o re v e r yd a t a - b i t s ；d e s i g n i n gas e r i e so fd a t as t r u c t u r eo f t a b l e si nr e l a t i o nt oa l l o c a t i n gd a t a b i t s ，a n di n t r o d u c i n gt h ea l l o c a t i o np r o c e s s o fd a t a b i t s s e c o n d l y , t h ew r i t e ri sr e s p o n s i b l ef o rs o f t w a r ed e s i g no fa l l o c a t i o n m a n a g e m e n ts y s t e m ，i n c l u d i n gt h em o d u l eo fu s e ri n t e r f a c ea n da l l o c a t i o n d a t a - b i t s ，a n di m p l e m e n t i n gi tb yp r o g r a m m i n g l a s t l y , t h ew r i t e ri sr e s p o n s i b l ef o rd e s i g n i n gt h et e s t i n ge x a m p l eo f e x p e r i m e n t ，a n dc h e c k i n go u tt h ec o r r e c t n e s so fa l l o c a t i o nm a n a g e m e n ts y s t e m a n dp r o g r a mb yi t t h et e s t i n gr e s u l tc a nv a l i d a t et h ec o r r e c t n e s so fa l l o c a t i o nm a n a g e m e n t s y s t e ma n dp r o g r a m k e y w o r d s ：t e r n a r yo p t i c a lc o m p u t e r ；d a t a b i tm a n a g e m e n t ；s t a t i ca l l o c a t i o ns t r a t e g y v i 上海大学硕上学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 本论文使用授权说明 期： 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：纽导师签名：钮日期：啦广 i i 上海人学硕士学位论文 第一章绪论 1 1 电子计算机资源管理策略概述 电子计算机系统中的资源包括硬件资源和软件资源，其中硬件资源包括 c p u 、外部设备、存储器等，软件资源包括各种系统软件、应用软件、编译软件 等。对于每一种资源，系统一般都有多种相应的管理策略对它进行管理。例如， 对于c p u ，根据操作系统的要求不同，c p u 管理策略不同。常见的进程和作业 调度算法有很多种，如先来先服务调度算法( f c f s ) 、轮转法、优先级法、最短 作业优先法( s j f ) 、最高响应比优先法( h r n ) 等【3 】；存储器资源包括内存和外 存，由于内存价格昂贵且容量小，操作系统为提高内存利用率采用了多种管理策 略。常见的内存管理策略有分区管理、页式管理、段式管理和段页式管理等。为 进一步改进现有内存管理策略，很多学者对其进行了研究【4 - 1 0 1 ，以及研究针对嵌 入式系统、l i n u x 系统等环境下的内存管理策略 1 1 1 7 】。除了内存管理策略外，还 有处理器、时间等其它资源的管理策略 1 8 乏3 1 。 虽然电子计算机中系统对各种资源的管理策略有很多种，但没有一种管理策 略能直接应用在本文的研究课题中，原因是当前电子计算机中的数据位数仅数十 位，所以目前成熟的操作系统中都没有高数据宽度管理技术。因此，本文研究的 技术是伴随光计算机的巨位数特点而生的全新课题。 1 2 光学计算机的位数资源管理需求 光的互不干扰性使得光学计算方法具有空间巨并行性，光的这种特性意味着 光学计算能拥有很高的数据宽度。本课题组研究的三值光学计算机使用技术成熟 的液晶显示器作为空间调制器，它的各种运算器都拥有很高的数据宽度 2 4 。3 0 1 。例 如，2 0 0 7 年初，我们用面积仅为3 8 m m x 6 5 5 m m 的单色液晶显示器就研制成功数 个3 6 0 位的三值逻辑光学运算器模型，而且只需更换面积稍大一点的液晶就能使 上海人学硕士学位论文 三值逻辑光学运算器的运算位数成倍增加。由此可见三值光计算机硬件的确拥有 很高的数据宽度。 三值光计算机拥有高数据宽度的特点使得它能够应用在一些特定的应用领 域，如大数据运算、大宗数据运算、结构化数据运算等领域。如何管理好三值光 计算机的高数据宽度，使得它能高效的应用在上述领域中，是充分发挥三值光计 算机运算能力的重要因素，也是数据位管理的主要功能。随着几个三百位量级三 值逻辑光学运算器模型的研制成功，如何管理三值光计算机高数据宽度成为当前 必须研究和解决的课题。2 0 0 7 年下半年我们开始对三值光计算机高数据宽度管 理技术进行全面研究。 同计算机其他资源管理方法相似，三值光计算机数据位资源管理也可以分成 资源分配管理和资源回收管理两大部分。作者的研究内容仅涉及分配管理部分， 回收管理部分由课题组另一成员完成。 1 3 研究内容 本文讨论的高数据宽度分配策略以2 0 0 7 年上半年研制成功的三百位量级三 值逻辑可重构光学运算器实验系统为管理对象。这个实验系统的总体结构如图 1 1 所示：其中a 为光源，b 为三态光编码器，c 为光学处理器，d 为三态光解 码器。b 调制数千条光线的状态，使其成为携带三值数据信息的光信号( 虚线所 示) ，这数千条信息光线在几条电信号( 实线所示) 的控制下同步运行；c 完成 光状态变换，依此完成信息变换( 计算) ；d 读出每一条信号光线携带的信息， 并将其转换成电子计算机可使用的形式。系统的核心三百位量级可重构光学 处理器，用型号为y m s g g 1 2 8 6 4 p 的单 色液晶点阵构成，该液晶点阵有1 2 8 x 6 4 个像素。依据降值设计理论 2 1 ，这个光学 处理器对不同的三值逻辑运算可以构造成 位数不同的处理器，其中位数最少的运算 卜 i 二 器为5 1 2 位。在实际系统中为充分利用液 a 晶资源，要对不同的运算构成不同位数的 图1 - 1 2 bcd 三值逻辑可重构光学运算器实验系统 上海人学硕士学位论文 处理器，但本文为了突出讨论“合理分配数据位 这一最基本技术，对这个问题 采用了简化措施规定所有处理器都为5 1 2 位。在这个简化下得到的结论可以 通过“数据位动态改变技术 应用于实际的光学处理器。 本文所述的管理系统运行在图1 1 的“控制系统 中，它对用户遮蔽掉了光 学处理器的硬件细节，提供了一个“由数据位组成算位”的运算资源逻辑结构。 这里的数据位及其编号由下层的光学部件驱动程序提供，至于数据位与图1 1 中 信息光线的对应( 可变的一对多关系) 、算位与信息光线的对应、运算器使用c 上像素的情况都由光学部件驱动程序实现，不属于本文讨论的问题。 1 4 本章小结 本章主要介绍了电子计算机中各种硬件资源的管理策略，随后介绍了课题的 产生背景三值光计算机数据位资源的管理需求，最后介绍了本文的研究对象 及主要研究内容。 上海大学硕士学位论文 2 1 相关概念 第二章数据位分配策略 在三值光计算机高数据宽度管理技术这个研究方向上，为便于管理高数据宽 度，金翊教授提出了算位、算道、算位类型、复合算位等新概念 1 】，下面分别对这 些术语进行阐述。 算位是表示一类数据的三值数据位数。它是分配、管理和使用三值光学计算 机数据位的基本单位，这一点与现代计算机科学中的“字节 概念相近。但是， 每个“字节都有8 位数据，而一个算位所包含的数据位数是可变的，它不限于仅 取一个值。我们称包含n 位数据的算位为n 算位，称n 为算位宽度。由于三值光计算 机使用电子计算机作为控制器，字节的概念还要在光计算机中保留，为避免日后 混淆，给三值光计算机系统的这一相近概念另取名称算位。 复合算位是指有限个算位组合有限次构成的算位。例如，1 个4 算位和1 个8 算 位组合成一个复合算位：1 2 算位。 算道是有限个算位的一个排列。算道是一个全新概念，它来源于大宗数据运 算和结构化数据运算等应用领域所提出的一个共同要求排列多个普通数据成 一个复合大数据。显然，若一个复合大数据中的每个普通数据用一个算位来运算， 按这些普通数据的排列来安排对应的算位排列，就构成了这个复合大数据对应的 数据位。鉴于三值光计算机的用户将以复合大数据来使用运算器，算位的排列就 成为有重要意义的独立概念，因此给它定义一个专用名称算道。 算位和算道只考虑了数据位数，没考虑数据的运算规则，如果光计算机只有 最基本的运算器，大多数运算规则由软件利用基本运算器完成( 与现行电子计算机 的策略相同) ，这2 个概念就可以满足高数据宽度管理的需要。但是，光计算机为 了发挥光的巨并行性，会不断增加运算器，以至于大多数运算规则都是靠专门的 运算器完成，这时硬件管理必然要增加对光运算器的管理模块，于是对每个算位 就要考虑使用哪个光学运算器，即要给算位赋予运算规则，这就又引出2 个新概念： 4 上海大学硕士学位论文 算位类型和算道类型。算位类型是定义了运算规则的算位。算道类型是有限个算 位类型的一个排列。 本文仅涉及算位、复合算位概念。在这些新概念的基础上，文献 1 描绘了一 个管理光学计算机众多数据位数的思想，但没有给出具体的实现方案。 2 2 数据位的静态分组 三值光计算机拥有很高的数据宽度，如何管理它是一个全新的研究课题，且 没有前人的工作可以借鉴。为解决这个新研究领域中遇到的主要问题，本文尝试 采用数据位的静态分组策略进行解决。 数据位的静态分组是指：系统在初始化时，将所有数据位按某种策略分成几 个宽度不等的组，在系统运行的整个过程中，这些数据位的分组不能改变，但是 不排除系统每次在初始化时采用不同的分组策略。 数据位的静态分组策略可能有很多种，文献 1 中提出了一种分组策略：将数 据位按照1 、5 、1 0 、2 0 、3 5 算位进行分组，共5 个组。本文在此基础上提出了一 种新的分组策略：将数据位宽度划分成1 、2 、4 、8 、1 6 、3 2 、6 4 、1 2 8 、2 5 6 、5 1 2 算位，共1 0 个组。 为对这两种分组策略进行比较，作者编写了一个程序进行实验。统计当用户 输入的数据位宽度在1 5 1 2 之间( 包括1 和5 1 2 ) 时，将文献 1 】的分组策略与本 文的分组策略相比，所需要组合的算位个数相等和少的情况，实验统计结果分别 如表2 1 和表2 2 所示。 表2 1两种分组策略组合算位的比较结果( 1 ) 算位组合组合算位组合组合算位组合组合 种类算位1算位2种类算位1算位2种类算位i算位2 1113 6 l ，3 5 4 ，3 2 5 7 1 ，1 , 2 0 ，3 5 1 , 8 ，1 6 ，3 2 6 1 , 52 ，4 3 7 1 ，1 ，3 51 , 4 ，3 2 6 2 1 ，1 ，5 ，2 0 ，3 52 ，4 ，8 ，16 ，3 2 7 1 ，1 ，51 , 2 ，4 4 05 3 58 3 26 3 1 ，1 ，1 ，5 , 2 0 ，3 51 ，2 ，4 ，8 ，1 6 ，3 2 2 2 1 ，1 ，2 02 ，4 ，1 6 4 1 1 , 5 ，3 5l ，8 ，3 2 8 5 5 ，1 0 ，3 5 ，3 51 , 4 ，1 6 ，6 4 2 3 1 ，1 ，1 ，2 01 , 2 ，4 ，1 6 5 0 5 ，1 0 ，3 5 2 ，1 6 ，3 2 1 0 6 l ，3 5 ，3 5 ，3 5 2 ，8 ，3 2 ，6 4 2 6 1 , 5 ，2 02 ，8 ，1 6 5 1 1 ，5 ，1 0 ，3 5l ，2 ，1 6 ，3 2 1 0 7 1 ，1 ，3 5 ，3 5 ，3 51 , 2 ，8 ，3 2 ，6 4 l ，1 ，1 ，2 ，1 ，2 0 ，8 ，1 6 ，1 , 3 5 ，3 5 ，3 5 ，1 , 2 ，4 ，8 ，16 ， 2 75 62 5 5 5 , 2 0 8 1 63 53 2 3 5 ，3 5 ，3 5 ，3 53 2 ，6 4 ，1 2 8 5 上海大学硕+ 学位论文 表2 - 1 中组合算位1 和组合算位2 分别表示采用文献 1 和本文的分组策略所 需组合的算位类型。例如：算位种类6 对应“组合算位1 ”列的值为：1 、5 ，表示 按照文献 1 的分组策略，6 算位由1 和5 算位组合而成。从表2 一l 可以看出：采用 两种分组策略，仅有2 1 种算位所需组合的算位个数相等。 表2 2 两种分组策略组合算位的比较结果( 2 ) 算位种类组合算位1组合算位2算位种类组合算位1 组合算位2 5 5 1 ，4 6 1 1 , 5 ，2 0 ，3 51 , 4 ，8 ，1 6 ，3 2 1 01 0 2 ，8 7 03 5 3 5 2 ，4 ，6 4 1 1 1 ，1 0l ，2 ，8 7 l 1 ，3 5 ，3 51 , 2 ，4 ，6 4 1 5 5 ，1 01 ，2 ，4 ，8 7 5 5 ，3 5 ，3 51 , 2 ，8 ，6 4 2 02 0 4 ，1 6 9 0 2 0 ，3 5 ，3 5 2 ，8 ，1 6 ，6 4 2 1 2 0 ，11 ，4 ，1 6 9 1 1 ，2 0 ，3 5 ，3 51 ，2 ，8 ，1 6 ，6 4 2 5 5 , 2 01 , 8 ，1 6 9 5 5 ，2 0 ，3 5 ，3 51 ，2 ，4 ，8 ，1 6 ，6 4 3 0 1 0 ，2 02 ，4 ，8 ， 1 0 5 3 5 ，3 5 ，3 51 ，8 ，3 2 ，6 4 3 1 1 ，1 0 ，2 01 , 2 ，4 ，8 ，1 6 l l o 5 ，3 5 ，3 5 ，3 52 ，4 ，8 ，3 2 ，6 4 3 53 5 1 , 2 ，3 2 1 1 1 1 ，5 ，3 5 ，3 5 ，3 51 ，2 ，4 ，8 ，3 2 ，6 4 4 5 1 0 ，3 51 ，4 ，8 ，3 2 1 1 5 1 0 ，3 5 ，3 5 ，3 5 1 ，2 ，1 6 ，3 2 ，6 4 4 6 1 ，1 0 ，3 52 ，4 ，8 ，3 2 1 2 5 2 0 ，3 5 ，3 5 ，3 5 1 ，4 ，8 ，16 ，3 2 ，6 4 4 7 1 ，1 ，1 0 ，3 51 ，2 ，4 ，8 ，3 2 1 2 6 1 ，2 0 ，3 5 ，3 5 ，3 52 ，4 ，8 ，16 ，3 2 ，6 4 5 5 2 0 ，3 51 , 2 ，4 ，1 6 ，3 2 1 2 7 1 ，1 ，2 0 ，3 5 ，3 5 ，3 51 ，2 , 4 ，8 ，1 6 ，3 2 ，6 4 6 0 5 , 2 0 ，3 54 ，8 ，1 6 ，3 2 1 7 5 3 5 ，3 5 ，3 5 ，3 5 ，3 51 , 2 ，4 ，8 ，3 2 ，1 2 8 表2 2 与表2 1 中表头所表示的意义相同。由表2 2 可知：采用文献 1 的分组 策略，仅有3 0 种算位所需组合的算位个数比本文的分组策略所需组合的算位个数 少。 因此，本文的分组策略与文献 1 】的分组策略相比，它有以下几方面的优点： 首先，它能更好的满足大数据位运算需求，它有最大数据位宽度达到5 1 2 算 位的分组，而文献 1 的分组策略中，最大数据位宽度只有3 5 算位。当用户申请大 数据位运算时，采用文献 1 的分组策略平均需要组合更多个算位才能满足需求。 假定超过1 0 0 算位为大算位，从表2 2 可以看出：在1 0 1 5 1 2 算位之间，采 用该种分组策略仅有8 种算位需要组合的算位个数比文献 1 需要组合的算位个数 多，其余的4 0 1 种算位( 除去组合算位个数相等的3 种算位) 需要组合的算位个 数比文献 1 需要组合的算位个数少。 其次，采用本文的分组策略，系统在构成任何一种算位( 不超过5 1 2 算位) 给用户时，平均需要组合算位的数量较少。 6 上海大学硕士学位论文 假定用户输入的运算数据请求中，按每种算位( 1 - 5 1 2 算位) 各请求1 次且仅 1 次计算，采用本文的分组策略与文献 1 的分组策略相比，系统需要组合的算位 个数少的算位有4 6 1 个，占请求算位总数的9 0 0 4 。 再次，系统在分配任何一种算位( 不超过5 1 2 算位) 给用户时，系统参与组 合算位的每个分组中最多只需要一个分配单位。 根据本文提出的数据位静态分组特点，它是按照2 的整数次幂进行划分数据 位，当把划分的数据位按其宽度从高到低进行排列之后，我们可把它们看作电子 计算机中采用二进制表示的“权”。由于二进制数每个比特位上的值为0 或1 ，并 且在它能表示的数据范围内，它能表示任何数。因此，在1 5 1 2 算位之间，系统 分配任何一种算位给用户时，在参与组合的分组算位中，最多只需要一个分配单 位。 因此，采用本文的分组策略，可以减少系统分配数据位资源时查找算位资源 表的数目，从而提高分配策略的运行速率。 当分组策略确定后，确定为每种算位各分配多少个单元是困难的。若小算位 分配的单元数较多，会使大算位拥有的单元个数少，当用户申请大数据位资源时， 一般需要组合较多的小算位才能实现，这会增加系统的时间开销；而若大算位分 配的单元个数较多，会使小算位拥有的单元个数少，当用户申请大宗数据运算时， 就会使系统有很多资源空闲，但是系统又不能通过拆分这些空闲资源分配给用户 的这种情况经常出现。在系统运行过程中，虽然数据位的分组和划分都不能改变， 但是系统在初始化时，可采用不同的分组和划分策略。 因此，系统在初始化时，可针对不同应用领域，采用不同的数据位划分策略。 若运算领域是大数据位运算，就将数据位集中划分到大算位上，使大算位拥有较 多的分配单位数；若运算领域是大宗数据运 算，就将数据位主要划分至j j d , 算位上，使小 算位拥有较多的分配单元数；若应用领域未 知，可采用平均划分数据位到各种算位，使 各种算位拥有的单元数大致相等。 本文为突出讨论“合理分配数据位这 表2 - 3 数据位划分表 数据位算位数据位算位 编号种类编号种类 d ( 0 0 0 0 01 ) 1 d ( 0 2 0 0 3 f ) 3 2 d ( 0 0 2 - - - 0 0 3 ) 2 d ( 0 4 0 0 7 f ) 6 4 d ( 0 0 4 - 4 ) 0 7 ) 4 d ( 0 8 0 - 0 f f ) 1 2 8 d ( o o s - - - o o f ) 8 d ( 1 0 0 i f f ) 2 5 6 d ( 0 1 0 m ) i f ) 1 6 d ( 0 0 0 - 0 0 0 ) 5 1 2 最基本技术，不考虑用户的特定应用领域，使数据位划分后各种算位所拥有的 7 上海大学硕士学位论文 单元数大致相当。数据位划分结果如表2 3 所示。表2 3 中数据位编号d ( i ) 中的i 采用十六迸制数表示，除1 和5 1 2 算位的分配单元数分别为2 和0 外，其余算位 的分配单元数全部为1 。 从表2 3 可以看出，采用本文的分组策略，有它的不足之处：每组算位所拥有 的分配单位数很少，当把5 1 2 位数据位资源划分到5 1 2 算位时，其它算位种类所 拥有的分配单元数全部为0 。当用户申请数据位运算时，系统可能经常出现所需算 位资源紧缺现象，导致较多的用户请求被挂起，从而严重影响整个系统的运行速 率。为克服这一缺点，本文中采用了给每个数据位设置多个算位属性的措施。 2 3 数据位的算位属性设置 当某个数据位被划分到n ( n 为正整数) 算位后，它就必须和另外n 1 个被划分 到n 算位的数据位一同被分配、管理和使用，为突出这一特征，称这个数据位具 有n 算位属性。 本文中为增加每种算位的可分配单元数，并为使每个数据位具有更多的灵活 性，采用把一个数据位静态划分到多种算位中去的策略，即给每个数据位赋予多 个算位属性。例如，当给某个数据位赋予1 、2 、3 2 、5 1 2 算位属性后，系统既可 把它作为1 个1 算位来使用，也可把它作为1 个2 算位、1 个3 2 算位或1 个5 1 2 算位中的一位来使用，从而既增加了该数据位被使用的灵活性，又增加了l 算位、 2 算位、3 2 算位和5 1 2 算位的可分配单元数量。 给每个数据位设置多个算位属性后，每种算位所拥有的单元数会增加。但是 确定为一个数据位设置多少个算位属性比较合理是困难的。若数据位的算位属性 少，则在用户所需算位的数据 位资源紧缺时，可能有其它算 位的数据位资源空闲，这会降 低数据位资源的利用率；若数 据位的算位属性过多，分配数 据位时就要查找和修改算位 资源表中较多的项，这会增加 表2 4 算位属性设置表 磊淤竺 l2481 63 26 41 2 82 5 65 1 2 数据位编号 d ( 0 0 0 0 0 3 ) t t tt d ( 0 0 4 , - - 0 0 7 ) t t t t d ( 0 0 8 - 4 ) 1n t ttt d ( 0 2 0 - 0 3 f ) t tt d ( 0 4 0 - - 0 7 f ) t tt d ( 0 8 0 - - o f f ) t tt d ( 1 0 0 1 7 f ) t tt t d ( 1 8 0 一i f f ) tt t 上海人学硕上学位论文 系统的时间开销。折中考虑，本文给每个数据位设置3 或4 个算位属性。 表2 4 是数据位的算位属性设置情况，其中第1 列的d ( i ) 是数据位编号，i 采 用3 位十六进制数编码；第l 行( 表头) 中的数字是各算位的数据位宽度，共指定了 l o 种算位宽度。表中的t 表示该行的数据位具有该列的算位属性。表2 4 中每个 数据位除都有5 1 2 算位属性外，还有2 3 个其他算位属性。 由表2 4 可知：1 、2 、4 、8 、1 6 、3 2 、6 4 、1 2 8 、2 5 6 、5 1 2 算位所拥有的分配 单元数分别为：4 、4 、7 、7 、6 、7 、4 、2 、1 、1 ，这与之前未给每个数据位设置 多个算位属性相比( 见表2 3 ) ，每种算位拥有的分配单元数明显增加。 2 4 算位资源表结构及用法 为使系统在分配数据位资源给用户时，能快速和方便的查找各种算位的数据 位资源，依据表2 4 生成系统的工作用表算位资源表( 表2 5 ) 。表2 5 是系统 初始化时的状态。 表2 - 5算位资源表 算 可 算算 可 算 起始 算 可 算 位 用 位起始状相关伉 用 位 数据 状相关位 用 位起始状相关 序态序号种序数据位态序号种 量 序数据位态序号种 里位量 类号类号类号 1 d ( 0 0 0 ) 1 5 , 2 9 1 6d ( 0 0 8 )l 1 0 ，11 ，2 9 2 9d ( 0 0 0 ) l 1 1 8 14 2 d ( 0 0 1 ) 1 5 , 2 9 1 7d ( 0 1 0 )1 1 2 ，1 3 ，2 9 3 0d ( 0 4 0 )l 2 5 ，2 6 - - r- _ 3 d ( 0 0 2 ) 1 6 ，2 9 1 8d ( 0 1 8 ) l 1 4 ，1 5 ，2 9 3 l9 ( q 鲤! l 2 7 ，2 8 4 d ( 0 0 3 ) 1 6 ，2 9 87 o- 3 27 _ 1 9d ( 0 2 0 、 l 2 33 2d ( 0 8 0 )l3 6 _ 5 d ( 0 0 0 ) 1 1 ，2 ，2 9 2 0d ( 0 2 8 1 2 33 3点a 0 ) 1 3 6 _ _ 6 蚴2 ) 一 l 3 , 4 ，2 9 2 1d ( 0 3 0 ：12 43 4d l o c 0 )l3 7 2 4 -一 7 d ( 0 0 4 ) 1 9 ，2 9 2 2d ( 0 3 8 ：12 43 5d ( 0 e 0 )13 7 8 d ( 0 0 6 ) l9 ，2 92 3d ( 0 2 0 )l 1 9 ，2 0 3 6d ( 0 8 0 )l 3 2 ，3 3 _- 3 7_ p l o c o ) 1 3 4 ，3 5 9d ( 0 0 4 )l 7 ，8 ，2 9 2 4d ( 0 3 0 ：1 2 1 ，2 2 6 44 _ _ o- 2 5 _ _d ( 0 4 0 )l3 03 8d ( 1 0 0 )l 4 0 ，4 2 1 0d ( 0 0 8 )1 1 6 ，2 9 1 66 _ -o- l ld ( 0 0 c )1 1 6 ，2 9 2 6d ( 0 5 0 l3 03 9d ( 1 4 0 )l 4 0 ，4 2 _ _ 4 71 2d ( 0 1 0 1l 1 7 , 2 9 2 7d ( 0 6 0 ；13 1 4 0d 0 0 0 )1 3 8 ，3 9 ，4 2 _ 1 2 8 2 1 3 d ( 0 1 4 ) l 1 7 , 2 9 2 8d ( 0 7 0 )13 14 1d ( 1 8 0 )14 2 1 4p ! ：q ! 璺) 1 1 8 , 2 92 5 6 14 2d f l 0 0 )13 8 4 l 1 5d ( 0 1 c )1 1 8 ，2 95 1 2l4 3d ( 0 0 0 ) l1 4 2 表2 5 中，“可用量 表示该种算位当时可用于分配的单元数量；“算位序 号 是给系统的每个算位赋予的标识号，用于区分各个算位；“起始数据位 表 示系统划分数据位到各个算位中的起始数据位，该列中的d ( i ) 表示的意义与表2 4 9 上海大学硕上学位论文 中的d ( i ) 相同；“状态”列中，“1 ”表示该行所在的算位处于空闲状态，可用于 分配，当某个算位被分配后，将其“状态值改为0 ，表示该算位处于已分配状态： “相关序号表示当某两个算位所构成的数据位中包含有相同部分的数据位时， 这两个算位就具有相关性。例如，表2 5 中，算位序号l 与算位序号5 和2 9 所包 含的数据位中，都含有数据位编号d ( 0 0 0 ) ，因此，与算位序号1 相关的算位序号 有5 和2 9 。 当需要分配某个算位给用户时，系统首先按顺序找到该算位对应的算位种类， 然后查看该种算位的“可用量”值。若算位的“可用量 值不为0 ，则将“可用 量值减l ，然后按顺序查找该种算位的“状态 列，找到可用算位( “状态 值 为1 ) 后，将此“状态 值改为0 ，并将对应的“算位序号 值拷入到“算位分配 表 ( 见表2 6 ) 对应的“算位序号”列中。再由此算位序号的“相关序号 值，分 别找到其对应的算位种类，将该相关序号所对应的“状态”值改为o ( 即改为忙) ， 并将该种算位的“可用量 值减1 ，若该相关序号的“状态”值原本是0 ，则相关 算位的“状态”值和“可用量”值都不需更改，至此一个算位分配完毕。 需要特别说明的是：系统中唯一的一个5 1 2 算位包含了所有的数据位资源。因 此，只要有任意一个算位被分配后，系统都不可能再分配5 1 2 算位，所以在表2 5 各算位的“相关序号 列中不需要给出5 1 2 算位的序号4 3 。系统对5 1 2 算位作特 殊处理，其处理方法是：系统在分配算位时，只要分配了一个算位，就将5 1 2 算 位的“可用量”值赋0 ，并将算位序号4 3 的“状态 值改为0 。 2 5 算位分配表 算位分配表是分配管理系统的结果输出表，它被系统发送给下层的光学部件 驱动软件，用于提供为下层软件构造光学处理器所需要的各种信息，算位分配表 结构如表2 - 6 所示。下面对表头( 第一行) 中的各个字段表示的意义进行说明。 用户i d 是为 在多用户系统中， 系统能够区分不 表2 - 5 算位分配表 用户任务运算表 i di di d f s s os ls 2s 3 s ds 5 s 6 s ， s 8 s 9 同的用户，给每个用户赋予唯一的标识号，以保证系统能把运算结果返回给所需 1 0 上海人学硕士学位论文 用户，但本文研究对象是单用户系统，用户i d 在本文研究的系统中不用，系统给 其填充固定值。 任务i d 用于登记本次数据位资源申请的任务号，系统给用户提交的每个任务 赋予唯一编号，以便区分用户提交的各个任务。 运算表d 是系统根据用户输入的三值逻辑运算真值表计算得到的运算规则编 号。 f s 是系统分配给本次任务的复合算位编号，表2 6 初始化时f s 的值为0 。 s o s 9 是分配给这个任务的算位序号，这些算位序号构成一个复合算位，这个复合 算位由任务i d 和f s 共同标识。s o s 9 列中的值分别对应1 、2 、4 、8 、1 6 、3 2 、 6 4 、1 2 8 、2 5 6 、5 1 2 算位的算位序号，如果系统在本次算位分配过程中，没有用到 对应算位种类的算位序号，则其对应列中的值填充零。例如，某次算位分配过程 中，系统给该次任务分配的算位序号为6 、1 0 、2 5 ，其对应的算位种类分别是2 、 4 、1 6 ，则在生成的算位分配表中s o s 9 的值依次为：0 、6 、1 0 、0 、2 5 、0 、0 、0 、 0 、0 。 2 6 静态分配 三值光计算机最终将允许系统动态分配数据位资源给用户。动态分配是指： 用户将运算数据提交给系统后，系统既可一次性分配用户所需的全部数据位资源 ( 资源够分配情况下) ，也可将用户提交的数据分成很多组，以组为单位分配资源 给用户，组的大小由系统空闲资源和用户提交数据位数决定。限于三值光计算机 的研究现状，并且本文为解决数据位资源分配中的基本技术问题，采用了较为简 单的静态分配技术。 静态分配是指：一个任务( 进程) 在申请数据位资源时，一次性向系统提交全部 资源请求。若系统拥有该任务所需要的全部数据位资源，就用一次分配来满足这 个任务；若系统不能满足需求，就将这个任务挂起，直到系统回收到新的数据位 资源或者每隔一时间片之后，再来判断挂起任务的需求是否能得到满足，若能满 足，就取消挂起的任务，并分配数据位资源给它，若仍不能满足需求，就继续挂 起任务，直到下一次系统回收到资源或者时间片时间到期，再来判断任务需求是 上海大学硕士学位论文 否能满足，依此循环。 用户向系统提交运算数据后，系统在分配数据位资源时，首先确定用户“运 算数据最大位数大小。系统根据“运算数据最大位数”确定复合算位大小，若 复合算位不是单一算位，系统就需组合多个算位才能构成复合算位。在构成复合 算位时，如果考虑算位冗余，就有多种构成方案，例如考虑冗余位的不同，构成 的复合算位就不一样。为了充分利用数据位资源，构成复合算位时不考虑算位冗 余，即在构成复合算位时，必须遵守以下原则： ( 1 ) 系统在计算构成复合算位所需要的算位种类时，不能直接考虑冗余分配， 而是经计算得出的算位种类之和恰好等于复合算位大小。例如，若复合算位是1 5 算位，系统不考虑直接分配1 6 算位，而给出的运算结果必须是1 、2 、4 、8 算位。 ( 2 ) 系统在分配某种单一算位时，若该种算位没有空闲资源，系统不能分配算 位资源表中比该种算位大的空闲算位。例如，系统在分配4 算位时，若4 算位没 有空闲资源，系统不能分配空闲的8 算位、1 6 算位等其它算位。 为充分发挥三值光学计算机的巨位数特点，系统最终将允许一个任务请求复合 运算器一包含多种运算规则的运算器，但目前要解决的首要问题是实现数据位 数的分配技术，所以本文简化对问题的处理，假定每个任务都请求单一运算器。 一次数据位分配操作由用户任务向系统提交数据位资源请求触发。用户任务 向系统的用户界面程序输入运算真值表和运算数据。用户界面程序从用户送入的 运算数据中提取出“数据个数”和“数据最大位数”两个重要参数，并根据运算 真值表计算出运算表i d ，然后将这三个参数连同“用户数据存储指针 一并提交 给本数据位资源分配程序，其中“用户数据存储指针 指向的是保存了用户i d 和 任务i d 的输入缓冲区首地址，而用户i d 和任务i d 在用户向系统提交数据时确定。 本数据位资源分配程序按以下步骤进行算位分配： ( 1 ) 根据“数据最大位数 ，并按照上述“复合算位构成原则 计算构成复合 算位所需组合的算位种类，设所需算位种类个数为n 。若“数据最大位数除好 等于某个算位种类，则复合算位成为单一算位( 以下同) 。 ( 2 ) 将所需的算位种类按其宽度进行排序，本文选择按其宽度从小到大进行排 序。 ( 3 ) 选择排序后的第i ( i 为正整数，1 s i 5 n ，i 初值为1 ) 个算位种类，查看表2 5 1 2 上海人学硕士学位论文 中该种算位的“可用量 值是否为0 。若“可用量”值为0 ，说明系统没有该种空 闲算位来构成复合算位，生成“算位回收请求”并发送给回收程序，并根据回收 程序的回收结果判断是否将任务挂起。若回收程序给出的是回收成功信号，则分 配该种算位，否则，系统将该任务挂起，分配程序接着处理下一个用户请求；若 “可用量 值不为0 ，则进入下一步。 ( 4 ) 将该种算位的“可用量 值减1 ，并按顺序查找该种算位的“状态”列， 找到“状态 列值为1 的算位后，将其“状态 值改为0 ，并将本算位序号拷入表 2 - 6 的s o s 9 的相应位置中。然后根据“相关序号 将相关算位的“状态 值也由 1 改为0 ，并将该相关算位的“可用量”值减l ，如果该相关算位的“状态 值原 本是0 ，则其“状态 值和“可用量”值都不需更改。 ( 5 ) i 值加1 ，并判断i 值是否大于n ，即判断本次所需的所有算位种类是否都 处理完毕，若i 值大于n ，就转到下一步，否则转到( 3 ) 开始执行。 ( 6 ) 将表2 6 的“f s 值加l ，并将s o s 9 中未用到的算位种类对应位置填充零。 ( 7 ) 由“用户数据存储指针”找到用户i d 和任务i d ，并将其值分别填入表2 - 6 的相应位置中。 ( 8 ) 将表2 - 6 中信息发送给光学部件驱动程序，光学部件驱动程序利用这些信 息来构造光学运算器。 ( 9 ) 系统根据用户的“数据个数 和采用某种策略决定是否为用户再分配复合 算位。系统可以采用的策略有很多种，本文在这里采用的策略是：若用户的“数 据个数 减去“f s 乘以3 0 0 后的值仍大于0 ，就转到下一步，进行再分配一个复 合算位的操作；否则，直