（计算机科学与技术专业论文）cam存储器功能模型的研究与实现.pdf

国防科学技术大学研究生院学位论文 摘要 随着i n t e m e t 的高速发展，网络流量越来越大，网络业务需求也不断发展变化， 对路由器、网关等硬件互联设备的要求越来越高。c a m 的高速查找特性和f p g a 技术的广泛应用，使得当前网络中高速路由查找技术、报文分类和入侵监测等很 多关键技术都采用c a m 和f p g a 结合的解决方案。 c a m 功能模型研究和实现，完善了f p g a 功能验证中外围芯片的支持库，方 便了f p g a 功能验证过程，加快了f p g a 设计的开发过程。 本文的主要工作和创新点包括： 1 详细分析了国内外功能建模的方法和过程，阐述了f p g a 逻辑测试过程和 f p g a 逻辑测试中器件功能模型建立方法； 2 针对c 触功能建模，详细的分析了c a m ，提出了c a m 功能模型框架， 并针对c 蝴功能模型的核心高速查找引擎，研究了国内外在查找引 擎中常用的查找算法； 3 提出了基于顺序查找引擎、基于h a s h 查找引擎和基于树查找引擎的3 种 c a m 功能模型设计，并实现了这3 种不同c a m 功能模型； 4 从理论上对这3 种基于不同查找引擎的c a m 功能模型进行了分析和比 较，并总结了它们之间的优缺点； 5 用v e r i l o g 实现了基于顺序查找的c a m 功能模型，在m o d e l s i m 环境下通 过了正确性验证，并应用于c l a 智能网卡逻辑设计功能验证中。 综上所述，本文对c 伽订功能模型设计进行了一系列的研究，研究成果对于 f p g a 设计具有重要意义。 主题词：c a m ，功能模型，功能验证，查找引擎 第i 页 国防科学技术大学研究生院学位论文 a bs t r a c t a st h ei n t e m e td e v e l o p ss oq u i c k l y ，t h ed a t af l o wi nt h en e t w o r kb e c o m e sb i g g e r a n db i g g e r ，a n dt h eb u s i n e s sr e q u i r e m e n tf o rt h en e t w o r ki sv e r ym u c hd i f f e r e n tf r o m b e f o r e h e n c e ，i tp o s tag r e a tc h a l l e n g ei nd e s i g n i n gt h eh a r d w a r eu n i t so ft h en e t w o r k ， s u c ha sr o u t e r s g a t e w a y s a n ds o0 n t h ef e a t u r eo fh i g hs p e e df o rc a ma n dt h ew i d e u s eo ff p g ah a sm a k et h ec o m b i n a t i o no ft h e mak e ys o l u t i o nt oi m p l e m e n t i n gt h e h i g h s p e e dr o u t ea n dp a c k e ts w i t c h i n g ，i d s ，a n ds oo n t h er e s e a r c ha n dr e a l i z a t i o no ff u n c t i o nm o d e lf o rc a me x p a n d st h el i b r a r yf o r p e r i p h e r yc h i pu s e df o rf u n c t i o nv e r i f i c a t i o ni nf p g ad e s i g n ，f a c i l i t a t et h ep r o c e s so f f u n c t i o nv e r i f i c a t i o na n ds h o r t e nt h ed e v e l o p m e n tp e r i o do ff p g a t h em a i nt a s k sa n dt h ei n n o v a t i o n si nt h i sp a p e ra r ei i s t e db e l o w ： 1 w ea n a l y z et h ee x i s t i n gm e t h o d sa n dt h em a i np r o c e s so ff u n c t i o nm o d e l i n g a n de x p a t i a t eo nt h ep r o c e s so f1 0 9 i ct e s to ff p g a d e s i g na n dt h em e t h o d so f d e v i c ef u n c t i o nm o d e l i n gi nt h el o g i ct e s to ff p g ad e s i g n 2 w ep r o p o s eaf r a m ef o rc a m sf u n c t i o nm o d e la f t e ra n a l y z i n gt h ec a mi n d e t a i l t h e n ，w ep a r t i c u l a r l ys t u d i e ds o m ep o p u l a rs e a r c h i n ga r i t h m e t i cw h i c h w a st h ec o r ep a r to fc a m sf u n c t i o nm o d e la n du s e dal o ti ns e a r c he n g i n ef o r e n h a n c i n gt h ep e r f o r m a n c eo fh i g h s p e e ds e a r c h i n ge n g i n e 3 w eb r i n gi na n di m p l e m e n tt h r e ef u n c t i o nm o d e l s ，i n c l u d i n gs e q u e n t i a ls e a r c h e n g i n e h a s h f u n c t i o ns e a r c he n g i n ea n dt r e e - l e v e l e ds e a r c he n g i n e 4 i nt h i s p a p e r ，w ea n a l y z e a n dc o m p a r et h e s et h r e ef u n c t i o nm o d e l s t h e o r e t i c a l l ya n ds u m m a r i z et h ea d v a n t a g e sa n dd i s a d v a n t a g e sb e t w e e nt h e m 5 w ei m p l e m e n tt h es e q u e n t i a lf u n c t i o nm o d e lf o rc a mi nv e r i l o ga n du s et h e m o d e l s i mt os i m u l a t et oa s s e r tt h ec o r r e c t n e s so ft h i sm o d e l ，w h i c hi sa p p l i e d i nt h el o g i c a lf u n c t i o nv e r i 丘c a t i o no fc i ac a r d i naw o r d w ec o n d u c tal o to fs t u d yi n t ot h ed e s i g no ff u n c t i o nm o d e lf o rc a m a n do u ra c h i e v e m e n tm a k e sr e a ls e n s ei nt h ed e s i g no ff p g a k e yw o r d s c a m ，f u n c t i o nm o d e l ，f u n c t i o nv e r i f i c a t i o n ，s e a r c he n g i n e 第i i 页 国防科学技术大学研究生院学位论文 表目录 表2 1 示例的分类规则集合1 6 表4 1c a m 数据表3 3 表4 2c a m 内部寄存器表3 3 表4 3h a s h 入口表3 3 表4 4c a m 数据链表3 3 表4 5c a m 数据项链表管理表3 4 表4 6c a m 数据表3 8 表4 7c a m 内部寄存器表3 8 表4 8c a m 查找树中间节点数据定义3 8 表4 9c a m 查找树中间节点数据定义3 9 表4 1 0c a m 查找树维护表结构3 9 表4 1 1c a m 查找树维护表结构4 0 表4 1 2 三种c a m 模型的各种操作复杂度比较4 4 表4 1 3 三种功能模型的内存占用情况表4 6 表4 1 4 实际内存占用情况对比表4 6 第1 v 页 国防科学技术大学研究生院学位论文 图目录 图1 1c a m 结构2 图2 1 典型的i d e f 0 功能模型8 图2 2g t s t 模型的结构框架9 图2 3 工程系统的一种模型表示1 0 图2 4g t s t 模型的组织结构。1 0 图2 5f p g a 逻辑设计测试模型。1 1 图2 6h e r a r c h i c a lt r i e s 数据结构。1 7 图2 7s e tp n m n i n gt r i e s 数据结构18 图3 1c 气m 内部结构2 0 图3 2c a m 建模接口信号定义2 3 图3 3c 剐功能模型总体框架2 4 图3 4 查找引擎的基本框架2 5 图3 5 基于顺序查找引擎的c a m 模型总体结构2 6 图3 6h a s h 查找引擎结构2 7 图3 7 树查找引擎结构2 8 图4 1 顺序查找模型的数据结构2 9 图4 2 逻辑控制模块的结构3 0 图4 3 逻辑控制模块与其它模块接口3 0 图4 4 顺序查找引擎结构31 图4 5 读、写、删除操作处理流程3 l 图4 6 查找操作处理流程3 2 图4 7 表之间的关系3 2 图4 8 基于h a s h 的查找引擎模块结构。3 4 图4 9 写操作处理流程3 5 图4 1 0 删除操作处理流程3 6 图4 1 l 查找操作处理流程3 6 图4 1 2 基于树查找的功能模型的数据结构3 7 图4 13c a m 查找树3 8 图4 1 4 基于树的查找引擎结构4 0 图4 1 5 写操作处理流程4 1 图4 1 6 查找操作处理流程4 2 图4 1 7 删除操作处理流程4 2 第v 页 国防科学技术人学研究生院学位论文 图4 18c a m 查找树4 5 图5 1f p g a 逻辑设计测试模型5 0 图5 2c i a 智能网卡总体结构5 2 图5 3c i a 智能网卡逻辑验证结构5 3 图5 4 基于c a m 的报文规则过滤5 4 图5 5c a m 控制器5 5 图5 6c a m 功能模型与c a m 控制器之间的信号5 6 图5 7c a m 写操作5 6 图5 8c a m 读操作5 7 图5 9c a m 查找操作5 7 第v i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获缛冒防科学技术大学或其它教育规构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了喷确的说明并表示谢意。 学位论文题目：茧缝盎篮墨边能搓型鲢盟蕉量塞塑 学位论文作者签名：垒生叁垒垒、一，日期：2 刁年l 纠日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被鸯阕孝借阕；可以将学位论文i 砖全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存，汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题霹：垒垡盔焦墨麴熊搓型鲤熟塞蔓塞毽 学位论文作者签名：盛霆投 日期：b 刁年z 月z j 日 作者指导教师擞：型蛆一魄1 年脯p 国防科学技术大学研究生院学位论文 第一章绪论 1 1 课题背景 i n t e r n e t 的不断发展，网络的不断普及，一方面，在网络中传输的流量也越来 越大，特别是路由器链路速度将达到4 0 g ，6 0 g 甚至上百g b p s 。另一方面，网络 中各种各样的应用不断变化和发展，现在的i p 网络需要为用户提供更多服务类型 和更好的服务质量，要求路由器提供额外的处理机制来实现区分服务，报文分类， 安全入侵监测，防火墙访问控制，虚拟专用网，快速路由查找，网络地址转化， 等一些网络关键技术。 为了适应网络的数据流量越来越大的发展趋势，保证网络链路的通畅性，对 路由器性能提出了新的挑战如何快速路由。网络技术的发展，这些关键网络 技术都涉及查找匹配问题，而基于软件的查找匹配效率低下，传统的软件实现的 方法对于高速网络的发展显的力不从心。随着f p g a 技术的发展和成熟，f p g a 技 术方案的灵活性，f p g a 在网络中应用也越来越广泛。 c a m 芯片的快速查找匹配特性，使得c 川在网络中得到广泛的应用。c a m 芯片的快速查找匹配的特点，为网络中很多关键的应用提供了新的解决方案。可 以用c a m 来实现快速路由查找，报文分类，区分服务，入侵监测等需要快速查找 匹配的关键技术。 f p g a 技术硬件解决方案的引入和c a m 芯片的快速查找特性，解决了现实网 络和未来网络中遇到很多关键问题。在当前的互联网中，很多网络硬件互联设备、 接口设备、网络安全设备都使用f p g a 3 技术来开发和实现，如路由器，智能网卡， 网关等。 f p g a 的开发流程主要包括设计输入，功能验证，综合，布局布线，时序验证， 生成并下载b i t 或p r o m 文件，进行板级调试。在f p g a 开发流程的当中，属于 验证的有功能仿真和时序验证两个步骤，由于前仿真和后仿真涉及验证环境的建 立，需要耗费大量的时间，而在s t a 中对时序报告进行分析也是一个非常复杂的 事情，因此验证在整个设计流程中占用了大量的时间，在复杂的f p g m c 设计中， 验证所占的时间估计在6 0 - - 7 0 之间。相比较而言，f p g a 设计流程的其他环 节由于需要人为干预的东西比较少，例如综合、布局布线等流程，基本所有的工 作都由工具完成，设置好工具的参数之后，结果很快就可以出来，因此所花的时 间精力要比验证少的多。 其中，在f p g a 验证中最主要是功能验证。功能验证必需要建立功能验证环 境，功能验证环境包括验证工具、验证激励、外围芯片支持库和逻辑设计。目前 f p g a 设计中常用的外围芯片有s r a m 、d d r 、c a m 等芯片，s r a m 和d d r 芯 第1 页 国防科学技术大学研究生院学位论文 片的v e r i l o g 或v h d l 模型已经由它们的芯片产商提供了，但c a m 芯片的v e r i l o g 或v h d l 模型芯片产商没有提供，因而c a m 功能模型的研究具有重大的理论意 义和实践意义。 理论意义：c a m 功能模型的研究与实现，研究了c a m 功能模型的特点，总 结出c a m 芯片所具有的最大的功能特点一快速查找匹配，结合c a m 的快速查找 匹配和模型的硬件描述语言实现等特点，需要研究能符合这些要求快速匹配查找 算法，具有很大的理论意义。 实践意义：c a m 功能模型的研究与实现，可以提供基本的c a m 功能模型， 这对于使用到c a m 芯片的f p g a 设计具有很大的实践意义：完善了f p g a 逻辑功 能验证的外围芯片支持库，有利于f p g a 设计的逻辑功能验证，从而缩短整个 f p g a 产品开发周期。 1 2c a m 存储器概述 c a m 存储器是一组相关联存储单元的集合，这些单元是可以通过数据内容来 并行访问的，而并不一定要通过指定的地址来访问的。每一个相关联单元有硬件 存储能力和通过控制单元的数据广播来查找它的内容，然后指明是否匹配。典型 的c a m 结构 2 3 j 如下图所示。 图1 1c a m 结构 从上图可知c a m 的主要组成部分有： 比较寄存器：接收外部输入的比较数据，存储在比较寄存器中；掩码寄存器： 掩码寄存器用来屏蔽掉在比较过程中不需要比较的数据； 存储器组：存储器组有n 组相关联字组成，每一组相关联字都具有储存数据 和比较数据的功能； 字选择寄存器：根据输入的地址产生那些相关联字进行操作的信号； 第2 页 国防科学技术大学研究生院学位论文 优先译码器：接收从相关联字过来的比较结果信号，并对这些信号进行优先 译码，根据译码结果产生一个二进制的匹配地址定位和个匹配命中信号。 c a m 具有储存数据和并行数据查找的功能，c a m 最主要的功能是并行查找 功能。一次典型的c a m 查找操作过程为：首先，c a m 接收外部的查找命令并把 查找数据存储到比较寄存器中，比较寄存器和掩码寄存器的内容来共同组成系统 的一个查找字( s e a r c hw o r d ) ，这些查找字广播到每一组相关联字中，每一组相关联 字都有一个匹配链( m a t c h l i n e ) ，匹配链指示查找字与存储字是否一致( 匹配或不匹 配) ，匹配链把结果反馈到优先译码器中，优先译码器产生一个二进制的匹配位置 定位和一个匹配命中信号。 由于在c a m 存储器中可能存在多个字的同时匹配，因而使用了一个优先译码 器而不是简单的译码器。当有多个字同时匹配时，优先译码器选择最高优先权的 匹配地址映射到匹配结果，在c a m 中低地址字具有高优先权。 1 3 国内外研究的现状 目前建立器件模型的方法有两种：一种是从元器件的电学工作特性出发，把 元器件看成“黑盒子”，测量其端口的电气特性，提取器件模型，而不涉及器件的工 作原理，称为行为级模型。这种模型的代表是i b i s 模型和s 参数。其优点是建模 和使用简单方便，节约资源，适用范围广泛，特别是在高频、非线性、大功率的 情况下行为级模型几乎是唯一的选择。缺点是精度较差，一致性不能保证，受测 试技术和精度的影响。另一种是以元器件的工作原理为基础，从元器件的数学方 程式出发，得到的器件模型及模型参数与器件的物理工作原理有密切的关系。 s p i c e 模型是这种模型中应用最广泛的一种。其优点是精度较高，特别是随着建 模手段的发展和半导体工艺的进步和规范，人们已可以在多种级别上提供这种模 型，满足不同的精度需要。缺点是模型复杂，计算时间长。 s p i c e ( s i m u l a t i o np r o g r a mw i t hi n t e g r a t e dc i r c u i te m p h a s i s ) l 啦j 是最为普遍的 电路级建模软件，各软件厂家提供了v s p i c e 、h s p i c e 、p s p i c e 等不同版本s p i c e 软 件，其仿真核心大同小异，都是采用了由美国加州b e r k e l e y 大学开发的s p i c e 模拟 算法。s p i c e 可对电路进行非线性直流分析、非线性瞬态分析和线性交流分析。 被分析的电路中的元件可包括电阻、电容、电感、互感、独立电压源、独立电流 源、各种线性受控源、传输线以及有源半导体器件。s p i c e 内建半导体器件模型， 用户只需选定模型级别并给出合适的参数。 如今，涉及模拟和数模混合电路的s o c 设计日益增多。由于电路规模增大和 复杂度提高，传统的s p i c e 仿真器已不能满足设计需求。h d l 正在成为实际的快 速硬件原型，越来越多a s i c 设计者使用v h d l v e r i l o g 来执行和测序所有的“w h a t i f 关系，v e r i l o gh d l 既是一种行为描述的语言也是一种结构描述的语言，无论描 第3 页 国防科学技术大学研究生院学位论文 述电路功能行为的模块或描述元器件或较大部件互连的模块都可以用v e r i l o g 语言 来建立电路模型。v e r i l o g 模型可以是实际电路的不同级别的抽象。这些抽象的级 别和它们对应的模型类型共有以下五种： 系统级：用语言提供的高级结构实现设计模块外部性能的模型。 算法级：用语言提供的高级结构实现算法运行的模型。 r t l 级：描述数据在寄存器之间流动和如何处理和控制这些数据流动的模型。 门级：描述逻辑门以及逻辑门之间连接的模型。 开关级：描述器件中三极管和储存结点以及它们之间连接的模型。 h a m a n t o o t h t 4 1 等人提出了一种自底向上的模拟电路行为建模方法，展现了一 种当前技术水平下的从电路级到寄存器传输级的高级建模技术。k r i sg a j 5 l 等人介 绍了使用v e r i l o gh d l 建立r s f q 电路的功能模型的方法和技术。 9 中全面阐述 了v e r i l o g 的建模方法( 包括，层次化建模、门级建模、数据流级建模、行为建模、 开关级建模等各个抽象层次的研究) 。【7 】中使用v e r i l o gh d l 对c a t c h 进行建模。 在f p g a 功能测试中的器件功能建模方面， 8 , 9 】中研究了功能模型的建立方 法，说明了整个建模的流程和在建模过程中要注意的细节，还全面的阐述了基于 v e r i l o g 的建模方法。【1 0 】中提出了一种面向对象和基于组件的虚拟器件仿真建模 方法，这些方法具有良好的直观性、可扩展性和可重用性。 在过去几年f p g a 的应用越来越广泛，c a m 在通信系统设计领域正变得越来 越重要。国内外许多大学和机构的学者都对c a m 进行了研究，他们在c a m 的物 理结构设计6 , 1 1 】、c a m 的应用1 2 , 1 3 2 8 】、c a m 的f p g a 实现 1 4 , 2 5 2 6 1 等方面，都取得 了很大的成果。 对于可供f p g a 逻辑级仿真的c a m 功能模型的研究，文全刚【8 】等人研究了小 型的c a m 功能模型( c a m 中只有几百个数据项) ，而当前的c a m 一般都具有几万 甚至几十万个数据表项，对于大容量c a m 功能模型的值得去研究。 1 4 课题研究的内容 在互联网中，很多硬件设备( 如路由器、网关、智能网卡等) 都用使用了f p g a 硬件解决方案，c a m 在互联网f p g a 硬件解决方案中广泛的使用，c a m 功能模 型的建立完善了f p g a 功能验证的外围芯片支持库，同时方便了f p g a 设计的功 能验证，从而加快了f p g a 产品的开发速度。 针对c a m 在互联网领域中的广泛使用，本课题详细分析和研究了c a m 储存 器，阐述了常用的功能建模方法及其逻辑器件功能模型等，并在这些方法的基础 之上研究了c a m 功能模型建立过程，解决了c a m 功能建模的一些关键问题，并 提出了3 种基于不同查找引擎的c a m 功能模型体系结构，分别对3 种不同体系结 构的c a m 功能模型进行了设计实现，并针对3 种不同体系结构c a m 功能模型的 第4 页 国防科学技术大学研究生院学位论文 进行了性能分析和比较。 本课题另外还阐述了f p g a 功能验证方法，以及c a m 功能模型在c i a 智能 网卡功能验证中的应用。 1 5 论文的组织 第一章介绍本课题的有关背景知识，介绍了c a m 存储器，全面介绍了建模方 面的国内外研究现状，以及本论文的主要工作。 第二章介绍了常用的功能建模方法和逻辑器件功能模型，并基于c a m 功能模 型的核心快速查找，研究了国内外的一些查找算法。 第三章对c a m 进行了深入的研究，提出了c a m 功能模型总体结构框架，需 求分析、设计目标、总体结构和设计核心，并在这些基础上提出了3 种基于不同 查找引擎的c a m 功能模型的设计。 第四章根据设计方案，按照模块化设计思想，给出3 种基于不同查找引擎的 c a m 功能模型详细实现方案，从数据结构的定义到每一个模块的实现流程。对3 种基于不同查找引擎的c a m 功能模型进行了性能分析，详细分析了3 种功能模型 之间的优缺点，并得出了结论。 第五章阐述了f p g a 功能验证的重要性，f p g a 功能验证坏境的构建过程，分 析和设计了c i a 智能网卡的功能验证过程，实现了一个基于顺序查找引擎的c a m 功能模型并应用于c i a 智能网卡功能验证中。 第六章进行总结和下一步工作。 1 6 课题的研究成果 在本课题的研究中主要取得了如下成果： 1 深入的研究了c a m 存储器，研究了功能建模的方法及逻辑器件建模方法， 同时还研究了在查找引擎中常用的查找算法，以及各种算法的优缺点。 2 针对c a m 的内部结构特点和功能特性，提出了c a m 功能模型总体结构 框架，并根据c a m 功能建模的核心快速查找匹配，结合前面研究的查找 算法，设计了3 种基于不同查找引擎的c a m 功能模型结构。 3 针对3 种基于不同查找引擎的c a m 功能模型，分别对这3 种c a m 功能 模型设计了详细的实现方案，实现了基于顺序查找引擎的c a m 功能模型， 并在m o d e l s i m 环境下通过了验证。 4 从理论上对这3 种基于不同的查找引擎c a m 功能的性能进行了分析比 较，并得出这3 种模型适应不同应用环境的结论。 5 实现了基于顺序查找的c a m 功能模型，通过m o d e l s i m 环境下了的验证， 并应用于c i a 智能网卡的功能验证中。 第5 页 国防科学技术大学研究生院学位论文 第二章相关研究 2 1 功能建模方法 功能模型是一种包含了系统功能知识的模型，本质上是种描述性的模型。它 除了可以描述传统模型所描述的结构知识和行为知识外，还可以对功能知识和目 标知识进行描述。在现阶段国内外有关功能建模思想的各种文献中最常见的几种 功能建模方法有结构化的建模方法、面向对象的建模方法、g t s t 方法、i d e f 0 法 等，它们在实际中的应用都非常的广泛。下面将对这几种方法进行简单的介绍和 分析。 2 1 1 结构化的建模方法 结构化方法是软件工程产生以后首先提出来的软件开发方法，它是一种实用 的软件开发方法，它由三部分组成：结构化分析( s t r u c t u r e da n a l y s i s 简称s a ) ，结 构化设计( s t r u c t u r e dd e s i g n 简称s d ) 和结构化程序设计( s t r u c t u r e dp r o g r a m m i n g 简 称s p ) 。结构化的方法是一种面向过程的系统方法，它在7 0 年代后期由y o u r d o n ， c o n s t a n t i n e 及d em a c r o 等人提出，现己得到了广泛的应用和发展。结构化方法是 一种从问题空间到某种表示的映射方法，它主要由实体一关系图、数据流图和数 据字典组成。 结构化方法的思想是按系统分层的观点，在分析问题时首先站在整体的角度 以确保全局的正确，然后再一层一层的深入考虑和处理局部问题。把整个系统分 成多个模块，每个模块再继续细化，直到最低一级可以拿来编码的程度，比较有 条理性。这就是所谓的自顶向下( t o p d o w n ) 的分析设计思想。这样自顶向下的分 析设计后，其具体的实现过程便采用从底向上( b o t t o m u p ) 的方法一个模块、一个 模块的丌发，调试，然后再由几个模块联调，最后整个系统联调。整个系统开发 过程可化分为若干个工作阶段：系统规划阶段、系统分析阶段、系统设计阶段、 系统实施阶段、系统运行阶段。这五个阶段称之为系统的生命周期( l i f ec y c l e ) 。 结构化方法的主要缺点是：其一，工作量大、繁琐，同时导致开发周期过长。 要求在早期调查中就充分掌握系统的信息需求、信息处理过程及预先系统可能发 生的变化，这在实际工作中很难做到或者说几乎做不到。其二，s a 方法对现实世 界中的数据流进行分析，把数据流映射到分析结果中，这种方法简单实用，适用 于数据处理领域，但现实世界中有些需求不是以数据流为主干的，就很难用于此 方法。 2 1 2 面向对象的建模方法 第6 页 国防科学技术大学研究生院学位论文 面向对象建模的基本思想：面向对象的建模方法是一种对应于真实世界概念 的抽象思维方式，它按照问题领域的基本事物实现自然分割，按人们通常的思维 方式建立问题领域的模型。这样，从问题空间到求解空间是一种自然的映射，相 互间有着直接的对应关系。面向对象建模方法关心的是系统涉及的对象及其相互 间的联系，围绕组成问题领域的事物进行分析，将这些对象进行一般化处理，抽 象成类，建立类之间的关联，并确定多阶性( m u l t i p l i c i t y ) 。在面向对象的建模方法 中，对象是一个具有局部状态和一个操作集所组成的实体，可以表示为o b j e c t ：= ( o i d ，d s ，o s ，m i ) ，其中，o i d 为对象名称，d s = d l ，d 2 ，d i l ，为数 据结构集，o s = o l ，0 2 ，o m ) 为操作集，m i = m l ，m 2 ，m k ，为消息 名称集。 类则是对具有相同属性和操作集的对象的抽象，是一种数据结构。o o 方法中 数据封装原则的引入，极大降低了各部分代码之间的藕合度，使得在系统功能发 生改变时，只需改变涉及对象的类的代码即可，而类的继承机制的采用实现了代 码的重用性。数据封装和继承机制使系统具有更大灵活性，可以对需求功能的变 化，快速做出反应。 面向对象的建模方法采用功能模型、对象模型和动态模型来建立系统模型。 在实际应用中，面向对象建模方法根据其抽象方向可分为自底向上方法、自顶向 下方法和混合方法。自底向上方法通过用户需求文档中的每个句子来建立o o 对 象模型或动态模型，具有强调可追踪性的优点；自顶向下方法则通常使用判断从 问题领域中选择重要信息，抽象出需求模型，然后再对其进行细化，最后得出比 较详细的系统模型。在实际中，单独采用自项向下方法或自底向上方法都是比较 困难的，因而往往是把两种方法结合起来使用，即混合方法。 2 1 3i d e f o 方法 i d e f 0 t 3 i 】 3 2 】是i c a md e f i n i t i o nm e t h o d 的缩写，是美国空军在7 0 年代末8 0 年代初i c a m ( i n t e g r a t e dc o m p u t e ra i d e dm a n u f a c t u r i n g ) i 程在结构化分析和设计 方法基础上发展的一套系统分析和设计方法。i d e f 0 是一系列功能建模方法之一， 广泛应用在软件工程领域，计算机辅助设计领域和智能系统领域等。目前它也广 泛应用在自动制造，管理科学，当代集成系统制造等领域中。i d e f 0 模型用“方框” 和“箭头”来表示系统，如图2 1 所示。“方框”代表功能模块，“箭头”代表输入、输 出、控制。 对于图2 1 的i d e f 0 模型，i d e f 0 模型的公式化描述为i i = i i i i ，a i o m ，a i c n ， a i m j ) ，其中， a i = a 1 ，a 2 ， ，i = l ，2 ，代表系统功能模型中的第i 个功能单元。 a i l l = a i l l ，a i l 2 ，) ，1 = 1 ，2 ，代表模块中的第1 个输入单元。 第7 页 国防科学技术大学研究生院学位论文 7 1 3o a i o m = a i 0 1 ，a i 0 2 ， ，m = l ，2 ，代表a i 模块中第m 个输出单元。 a i c n = a i c l ，a i c 2 ，) ，n - - 1 ，2 ，代表a 模块中的第n 个控制逻辑单 a i m j = a i m l ，a i m 2 ，) ，j = 1 ，2 ，代表a 模块中的第j 个机械单元。 a 1 i l a 2 0 l 图2 1 典型的i d e f 0 功能模型 i d e f 0的基本思想是结构化分析方法，来源于 s a d t ( s y s t e ma n a l y s i sa n dd e s i g nt e c h n o l o g y ) 方法。它具有以下一组基本特色，这 些特色形成一种思维规则，适用于从计划阶段到设计阶段的各种工作。 全面地描述系统，通过建立模型来理解一个系统。 一般地说，一个系统可以被认为是由对象物体( 用数据表示) 和活动( 由人、机 器和软件来执行1 以及它们之间的联系组成，那至多只反映了一个侧面，这样的技 术很难说明系统的全貌。i d e f o 能同时表达系统的活动( 用盒子表示) 和数据流( 用 箭头表示) 以及它们之间的联系。所以i d e f 0 模型能使人们全面描述系统。 工程界对系统开发过程一般可安排几个阶段：分析( 确定系统将做什么) 、设计 ( 定义子系统及其接口) 、实现( 独立地创建子系统) 、集成( 把子系统联接成一个整 体) 、测试( 证明系统能工作) 、安装( 使系统能运行) 和运行( 使用系统) 。 ( 1 ) 目的与观点 目的是指建模的意义，为什么要建立模型。观点是指从哪个角度去反映问题 或者站在什么人的立场上来分析问题。功能模型是为了要进一步做好需求分析， 要实现预定的技术要求( 不论是对已有系统的改造还是新建系统) ，所以要明确是对 功能活动进行分析( 逐步分解) ，而不是对组织机构的分解。 ( 2 ) 区别“什么”( w h a t ) 和“如何”( h o w ) “什么”是指一个系统必须完成的是“什么”功能，“如何”是指系统为完成指定功 能而应“如何”建立。就是说，在一个模型中应能明确地区别出功能与实现间的差别。 i d e f 0 首先建立功能模型。把表示“这个问题是什么”的分析阶段，与“这个问 题是如何处理与实现”的设计阶段仔细地区别开来。这样，在决定解法的细节之f j ， 第8 页 国防科学技术大学研究生院学位论文 保证能完整而清晰地理解问题。这是系统成功开发的关键所在。 在设计阶段，要逐渐识别各种能用来实现所需功能的机制，识别选择适当机 制的依据是设计经验及对性能约束的知识。根据不同模型，机制可以是很抽象， 也可以是很具体的。重要的是，机制指出了“什么”是“如何”地实现的。 ( 3 ) 自顶向下分解 用严格的自顶向下地逐层分解的方式来构造模型，使其主要功能在项层说明， 然后分解得到逐层有明确范围的细节表示，每个模型在内部是完全一致的。 2 1 4g t s t 方法 g t s t ( g o a l t r e es u c c e s s t r e e ) 2 9 j 方法认为系统是通过一种逐级发展形成的， 模型是人们根据需要，从某一种观点上对系统的正确的描述，因而，它也用到了 一种等级结构来对系统进行建模，并且它将这种结构以树的形式表示了出来。在 它的构建中，首先将系统总的目标分为子目标，再将子目标继续进行细分，一直 分解到再分下去就会涉及到具体的物理系统为止，到此为止所形成的这一部分就 叫做目标树( g o a lt r e e ) 。然后再针对于每一个基本目标，描述出其实现路径，这一 部分便叫做成功树。 下面是g t s t 模型建立的思想基础： 首先，系统的建立是一个逐级发展的过程，比如，我们在设计一个电话系统 时，我们首先考虑的是一个总的目标，即通过这个设备能听到远方传来的声音， 并且还能将自己的声音传向远方。那么这一总的目标又可分为：声音信号的接收、 声音信号的转化、信号的传递、接受信号时发出警报等功能，确定了最基本的功 能之后，设计的任务就是寻找能够完成这些功能的部件。g t s t 模型的建立就是基 于这种考虑的，其基本结构框架如图2 2 所示。 目标 功能 子功能 i 系统组成部件 基本部件 图2 2g t s t 模型的结构框架 其次，g t s t 还认为：一个工程系统可以由图2 3 所示模型来表示。在这个模 型中，一个控制体围绕着这个系统，主要物质( c o m m o d i t y ) c l ，c 2 ，c m 进入控 制块，系统对其进行处理，从而产生输出物质( c o m m o d i t y ) c l ，c 2 ，c 。系统 需要一定的支持来使这种物质( c o m m o d i t y ) 守恒成为可能。因此，支持物质 第9 页 回 圃 标l|l一法泐ii弓盼昧u施徘ui； 甄钾o督u 脚m 1构 一 副粼幡水 一 国防科学技术大学研究生院学位论文 ( c o m m o d i t y ) s l ，s 2 ，s k 进入控制块，使处理过程变得简单，并以s 1 ，s 2 ， s l 的形式从系统和控制块中出来。 s l s z s i c l c 2 c m s ls 2s k 图2 3 工程系统的一种模型表示 g t s t 模型的组织结构如图2 4 所示： c l c 2 c n 成功树 图2 4g t s t 模型的组织结构 g t s t 模型的建立过程其实就是对系统进行分解的过程，步骤如下： 第一步，就是要确立系统总的目标，分解系统。分解的目的就是为了说明系 统为什么要由这些部分来组成，各组成部分又对目标的实现分别起到了什么样的 作用。这种功能分解充分表明了系统内在的设计思想、设计者的想法、系统实体 及其各部分所起作用。对于一个系统来说，它的g t s t 模型层次是任意的，分解 过程主要是凭人们的直觉而进行，而且这个分解过程还可能要重复多次，其层次 逐步细化，从而使模型逐步细化。 在g t s t 模型的建立过程中，并没有严格的规则对分解过程进行指导，也没 有规定每个等级所应有的抽象程度，在分解过程中只需遵循一些一般性的规则。 第1 0 页 一丁俐 国防科学技术大学研究生院学位论文 第一条规则就是当对目标或者功能进行分解时，必须保证从一个功能向下看，其 最近的功z 月, , 匕l f i 子功能应可以描述这一个父功能是如何实现的。而在一个复杂系统的 g t s t 模型中