（计算机系统结构专业论文）数据流硬分类器的研究与设计.pdf

东南大学硕士学位论文 摘要 随着计算机应用的飞速发展，数据流处理逐渐成为当前数据库领域新的研究热点。数据 流是一种新型的数据处理模型。在许多应用领域中管理的数据都是数据流的形式虽然数据 流中的数据的基本单位还是关系模型中的元组，但是与传统数据库中的数据不同，这类数据 不再是永久的关系形式，而是源源不断的到来，时间有序，瞬时变化的。大部分数据流处理 系统是采取软件方法设计。但是由于软件的处理速度比较慢，数据流来的速度又比较快，所 以软件处理数据流的速度相对就显得比较慢。很难保证数据处理的实时性要求，因此采用硬 件设计的数据流系统将具有极大的现实应用意义 本文在综合参考国内外同行对数据流分类器设计的基础上，设计了一种相对通用的硬件 数据流分类器。由于数据流本身的特点，许多传统的数据分类算法并不适合应用于数据流。 因为数据流不像传统数据那样静态存储在磁盘中，而是以流动方式出现的。因此许多数据如 果没有被保存将无法重新访问，所以基于数据流的分类算法只能通过对数据进行一次扫描完 成挖掘。如果数据流来的速度过快的话，由于内存无法存储全部数据，也使得数据流分类算 法只能利用有限的内存提取数据流的一个样本作为算法的输入数据，所以分类的结果也是近 似的，同时考虑数据流的特点，分类的结果也应该是实时的。论文在传统s p r i n r 算法的基 础上提出了一种新的适用于数据流环境的快速s 即一s p r i n t 算法，并在该算法的基础上更进 一步提出了并行算法p r l i 届_ s 踟一s p l l i n t 算法。同时在p r i l 乩_ s e u - s p r i n r 算法基础上 提出了硬件分类器的设计思想和设计框图 关键词：数据流，数据流分类算法，分类算法，分类器，s p r i n t 算法 东南大学硕士学位论文 a b s c r a c t 眦q u i c kd c i o p m e io fc o m p u t 盯印p l i 硒n 玳ao fd a m 拙a l n s m 柚a 画喀柚d i n a l r z m ga 砖毋u 啦i n t on s e a r c hh o t s p o t 蝴f l y d a t as t r e a m si san w d a t am o d e l i nm a n y a p p h 蕊d o n 五e l d s ，t h em n a 衄d a t a 撇勰p a t t c mo fd a t as t r e a m s 岫g hb a s i cu n i ti nd a t a s t x e a m si sa l s ot e r mi n 肥l a t i o nm o d e l , b u ti ti sd i f f e r e n tw i t hd a t ai nt r a d i t i o n a ld a t a b a s eb o c i u o e s u c hd a t ai sd om i e p e r m a n e n tb u tr e a c h i n gc o n t i n u o u s , 缸o r d e r e d , i n s t a n t a n e o u sc h a n g i n g m o s td a t as t r e a m s s y s t e mi sj 卫叩岫m t e db yw a yo fs o f t w m 4 a n dt h er a t et od e a lw i t hd a t a s t r e a m si s 蛆航s oh a r d w a r cd e s i g no fd a t as h e a m s s y s t e mw i l lb em o r ep r a c t i c a la c c o r d i n gt o s o l 呐v a r cd e s i g no fd a t as t r e a m s s y s t e m o nab a s eo fh o m ea n df o r e i g nd i 伊o f 出妇醴晦 c h s s i 矗c lp a p e rd e s i g n sau n h 酬h a r d w a r ea s4d a t as t r e a m s c l a s s i f i e r b e c a u s eo ft r a i to fd a t as t g e a m si 眦t f , m a n yt r a d i t i o n a ld a t ac h s s i f y i n ga l g o r i t h m sd on o tf i t t h ea p p l i c a t i o no fd a t as t a m s b e c a u s ed a t as t r e a m sa i e 删s t a t i c a l l ys a v e di nd i s ka st r a d i t i o n a l d a t a , i ta p p e a r sb yf l u i dw a y i fd a t a 缸n o ts a v e d , i tw i l ln o tb ev i s i t e da g b i n , s oc k 城 蚰窖o f i 山脚o n l yc a ns 锄t h ed a t ao mt i m ea n d 砒t h e 髓埘t i m ec o m p l e t et h ep r o c e mo fd a t a d 嬲s i f 衄i ft h ec o m m gr a t eo fd a t as t r e a m si 墨t o oq 峨t h e nc l a s s i f i e r 锄o n l yd e a lw i t h 肼晌no fw h o l ed a t a , t h er e s u l ti sw p 础a t ca n dt e a l - t i m e p a p e rb r i n g s 自o r w a r dt 栅 q u i c ka l i 鳓r i l h mc a l l e ds e u 册r d r ra c c o r d i n gd a t as t r e a m s c k c u m s t a m o nb a s eo fa l g o r i t l a n s e u - s p r i n t , p a p e rb r i n g sf o r w a r dp a r a n e la l g o d t l u nm l m e dp a r a iie i 塔e u - s p r 州：a lt h e 5 a m6 m o i l 曲曙b a s eo fa l g o r i t h mn a m e dp a r a i j e l - s e u - s p r i n t , p a p e rf u r t h e rb r i n g s f o “v a l dt h ed e s i g ni d e aa n da r c h i t e c t u r eo ft h eh a r d w a r ed s i b 札 k e y w o r d ：d a t as l r e a m & d a t a 蛐暇i m sd 髓醯f y i n ga l g o f i t h m , 6 i a 鹞i f 妒n g 蜊t h ：m ，d a s s i f 喝 s p r i n t 羽g ，i i l h ：m 东南大学学位论文 独创性声明及使用授权的说明 一、学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料与我 一同工作的同志对本研究所傲的任何贡献均已在论文中作了明确的说明并表示了谢意。 二i 关于学位论文使用授权的说明 东南大学、中国科学技术信息研究所、国家圈书馆有权保留本入所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文本人电子文档的内容和纸质 论文的内容相二致。除在保密期内的保密论文外。允许论文被查阅和借阅，可以公布( 包括 刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理t 签名， 导师签 日期： 璧 名 期 签 日 第一章绪论 1 1研究背景 第一章绪论 随着计算机应用的飞速发展，数据流处理逐渐成为当前数据库领域新的研究热点数据流 是一种新型的数据处理模型在许多应用领域中管理的数据都是数据流的形式。例如：对网 络进行检测时的i p 数据包，b a i d u 。6 0 0 9 l e 每天的获得的大量搜索信息，对股票进行分析时 的股票信息，电信公司的通话记录，传感器检测到的各类数据等等。尽管在这些大量的信息 资源中蕴含着具有巨大潜在价值的知识，不过由于这里面数据的量过于庞大，而且一直在不 停的快速增长，同时数据更新速度非常快，所以在里面迅速地挖掘有用信息变的尤为重要 因此。虽然数据流中的数据的基本单位还是关系模型中的元组，但是与传统数据库中的数据 不同，这类数据不再是永久的关系形式，而是源源不断的到来，时间有序，瞬时变化的 在数据流模型中，部分或者全部数据都是以一种连续的流的形式在线到达的，与传统的关 系模型相比，具有以下不同之处： 流的数据元素在线到达； 系统无法控制数据元素到达顺序； 数据流可能是无界的； 数据元素一经流过就不复存在，除非进行特别的处理( 如将数据元素存储在内存 当中) 。否则无法轻易重新使用这些数据元素。 由于数据流本身的特点，所以要对数据流进行挖掘，必须充分考虑三个限制性的关键因素： 时间，内存，数据量的大小所以许多传统的数据挖掘算法( 包括分类算法) 并不适合应用 于数据流因为数据流不像传统数据那样静态存储在磁盘中，而是以流动方式出现 由于数据流不断的更新，算法不可能同时处理所有的到来的数据流，所以挖掘到的结果也 在随时间不断地变化，也使得挖掘的结果不能是绝对精确的，是有局限性的同时，鉴于实 时性的要求，算法的时间复杂度必须较低，必须能够在内存中实现，不能进行内外存交换， 因为这样会浪费大量的时间因此，传统的数据挖掘算法如果不改进大多是不适合在数据流 上进行挖掘的而且由于软件的处理速度比较慢，数据流到来的速度比较快，所以采用硬件 设计相关的数据挖掘工具将具有极大的现实应用意义 1 2研究现状与分析 近几年来，国内外许多数据库研究者开始从事数据流相关技术的研究，并取得了一些研 究成果。目前已经有了许多研究项目。比较有代表性的项目包括s t r e 心，t e l e g r a p h 和a u r o r a s t r e a m 是斯坦福大学数据库研究组的一个项目，其目标是实现一个通用的数据流管理系统， 研究内容涵盖了数据流查询处理的各个方面，如资源管理，近似查询处理，数据流查询语言 的定义等方面t e l e g r a p h 是美国加州大学伯克利分校的研究项目，主要是基于自适应的查 询处理技术来处理连续查询，其中的t u p l er o u t i n g 和g r o u pf i l t e r 技术可以实现多查询操 作算子的共享，有效的降低了查询处理的内存开销。a u r o r a 是布朗大学，布兰代斯大学和麻 省理工学院三校联合研究的传感器网络中的数据流的查询操作的调度策略负载脱落技术以 及查询结果的q o s 等方面的问题。 由上可见，当前大多数与数据流相关的项目主要集中在数据流管理及查询处理方面，在 数据流挖掘方面的研究项目还不多见，主要有u i u c 的j h a n 领导下的小组在做这方面的工作。 国内，也刚开始在这方面有了一些探索，在数据流挖掘领域有很多有趣的问题值得探索，其 中怎样将已有的传统挖掘分类算法加以改进并移植到数据流环境中并用硬件的思想设计实 现一个高效的硬件数据流分类器是本文研究的重点 i 东南大学硕士学位论文 数据分类实际上就是从数据库对象中发现共性，并将数据对象分成不同几类的一个过 程在数据分类中，一个样本数据库被当作一个训练集，训练集中的每个元组都保持取样数 据库的所有属性，并且都有一个类的标识符与之对应分类的目标是首先对训练数据进行分 析，使用数据的某些特征属性，给出每个类的准确描述，然后使用这些描述，对取样数据库 中的其它数据进行分类，或者是为每个类产生更好的描述，也即分类规则。具体的说，分类 是一个两部过程第一步，建立一个模型，描述预定的数据类集或概念集。通过分析有属性 - 描述的数据库元组来构造模型假定每个元组属于一个预定义的类，由一个称作类标号属性 ( a a 鹞l a b e la 慨t e ) 的属性确定第二步，使用模型进行分类首先评估分类模型的预测 准确率。如果认为模型的准确率可以接受，就可以用它对类标号未知的数据元组或对象进行 分类，当然这里面也会有一个模型重建的操作 目前已有的分类方法有很多种，比如说决策树方法，贝叶斯分类法，人工神经网络方法， 关联分类法，k - t 邻近分类法，遗传算法，粗糙集方法，模糊集方法等等 在上述所有的算法中决策树算法特别适用于数据分类，因为决策树模型的思想能够很简 单容易的被人们理解，而且决策分类树也很容易转换为相应的分类规则决策树学习是一种 逼近离散值目标函数的有指导的学习方法，在这种方法中学习到的函数被表示为一棵决策 树学习得到的决策树也能被表示为多个i f - t h e n 规则，以提高可读性这种学习算法是最流 行的归纳推理算法之一，已经被成功的应用到从学习医疗诊断到学习评估信贷申请的信用风 险的广阔领域最重要的是相对其他方法决策树能够在构造速度快于前者的前提下获得相似 甚至有时候更精确的数据分类，所以本文打算选择决策树分类方法作为分类器使用的算法 决策树方法中适用于静态数据集的m 3 ，o 和a 噼传统分类方法需要存储和处理全部 训练样本，而对于动态的潜在无限的数据流，不断增加的训练数据量和待分类数据量为上述 分类系统提出了更高的需求，连续的数据流可能超出内存容量，也可能导致计算时问过长 传统的分类方法在处理海量数据时会出现性能下降或精度降低的问题为此，m m 研究人员 提出了一种快速的、可伸缩的，适合处理较大规模的决策树分类算法s l i q 该算法利用 属性表、类表和类直方图3 种数据结构来构造树，在决策树的构造阶段采用了预捧序技术， 并与宽度优先增长策略相结合，但是由于s u q 算法要求类表驻留内存，这限制了s i1 0 算 法处理数据的最大规模由此，m m 研究人员又提出了决策树分类算法s p r i n t ，该算法消 除了所有的内存限制，易于并行化，性能较好，并行化也更易于用硬件的思想进行设计，实 验表明：在s u q 的类表可以存放在内存的情况下，s l i q 的执行速度比s p r i n t 快，然而， 在训练集数据超过了s l i o 能承受的最大规模后，s p r i n t 的执行速度明显要比s il o 快 由上可知，s p r i n t 算法的所有特点都使得它非常适合移植到数据流应用的环境中来 虽然已经找到可以移植到数据流环境中的算法，但是在数据流分类的过程中，即使所有 有效的样本可以被系统处理，由于数据生成过程中不可估计的变化( 例如政治事件对股票价 格的影响) ，从历史数据中发现的分类模式对于几小时甚至几分钟之后接到的数据通常也是 无用的因此与静态数据分类处理不同。数据流分类挖掘必须首先解决概念漂移( d r i f t i n g c o n c e p t ) 的问题。h e l m b o l d 与l o n g 首先研究了概念随时间变化的概念漂移问题，漂移的速率 被定义为对于两个连续的样本目标函数不一致的概率 2 9 1 。并且提出了一种在固定数据集上 最小化不一致情况的算法，其复杂度为样本数量的多项式规模。然而，对于海量非固定的数 据流，漂移发生的实际速率事先无法知道，其算法的运行时问可能不确定地增加。数据流分 类器的研究为传统的分类技术提出了许多新的挑战，由于分类理论和方法在不同领域有着相 当广泛的应用，因此研究快速的、精确的，稳定的数据流分类系统具有极高的理论价值和应 用价值。 传统上，增量( 在线) 学习算法是从连续数据流中抽取模式主要的方法，增量归纳的基本 思想是，每当接收到一个实例时，更新一个已存在的模式比创建一个新的模式的代价低许多 2 第一章绪论 然而，增量算法具有几个不可避免的缺陷，比如对训练样本顺序的高敏感性、较非增量f 成 批处理) 方法需要更长的训练时间等。在处理以每秒几千个速度抵达的事务对象，当每个新 事例到来就更新的纯粹的增量方法是不切合实际的纯粹增量学习算法包括w n 0 1 矿螂、 c o b w e b 3 1 】和r r f ”垮。这些方法重点在于如何从固定的数据中产生分类模式的有效方法， 不太适合快速的数据流中相关模式的创建。 近几年数据流研究领域中有关流数据的分类问题研究比较活跃，出现了许多研究成果。 w 抽矧等提出一个通用框架用于挖掘概念漂移数据流，他们发现，迄今为止提出的数 据流挖掘算法并没有解决在进化数据上的概念漂移问题。他们提出使用加权分类器的组合来 挖掘数据流。模型中旧数据的过期特性依赖于数据分布他们使用合成和真实数据测试其算 法并比较了单个分类器和分类器组合的性能。算法组合了多个反映其期望精度的加权分类 嚣在不失精度的前提下选取部分分类器而不是全部分类器是该框架的一个可选方案 g a n f i “1 等开发了一个算法在插入和删除数据记录时维护模型此算法能够应用于任何 增量数据挖掘模型他们也描述为一种通用的框架，在两个数据集中根据其产生的数据挖掘 结果进行变化检测他们对上述两种技术进行了形式化成为两个通用算法：g e m m 与 f o c u s 。这两个算法已经应用于决策树模型和频繁项集模型。g e m m 算法接收一个模型类 和不受限的窗口选项增量模型维护算法，输出一个包括窗口无关与窗口有关块选择序列的模 型维护算法 n m h i 窖o s i 冽等开发了聊。这是- - - i 基于h o e f f d l n g 树的决策树学习系统它使用当 前最佳属性，考察的依据是所用的检验数据项的个数满足h o c f f d i n g 边界的统计测度 p a p a d i m i t r i o u p ，瞎提出a w s o m ( a i b i 昀l yw i n d o ws t r e a mm o d e l i n gm e t h o d ) 用于在传感 器网络中的发现感兴趣的模式他们开发了一个o n e - p a s s 算法增量更新模式其方法只需要 o i 晰储代价，其中n 为序列的长度他们使用小波系数作为压缩信息表示和相关结构 检测。然后在小波域上应用线性回归模型 冉掣“1 6 】等采用o n - d e m a n d 分类中c l u s t r e a m 的微簇思想，显示了高精度此技术 通过使用在每个簇中类分布的统计信息的方式，使用簇结果分类数据 d i 蜡吲等开发了基于p e a mc o u m t r 数据结构的决策树，用实验证明了算法快速且适 用于流应用 不过上面提到的这些已经存在的数据流分类模型和算法存在两方面问题，首先，都没有 较好地解决变化数据流上的概念漂移问题，分类精度偏低；其次，都没有以提高分类模型的 学习与分类速度为主要设计目标，分类器处理性能有待提高，难以适应工业实时控制应用的 需要。 为了进一步向现实应用靠近。为了能够进一步解决工业数据流的快速的分类，本文打算 设计一种基于决策树的在线分类系统，能够接收连续的数据样本流，对训练样本滑动窗口反 复应用分类学习算法，动态适应训练窗口的大小，并且根据当前概念漂移的速率调整模型重 建的频度。系统既不受数据流总体持续时间的影响，也不受到达样本的累计数影响有鉴于 s p r i w r 算法在可伸缩性，并行性方面具有相对其他决策树分类方法的优点，本文在s p r i n t 算法的基础上构建数据流分类模式，改造s p r i n t 为适于快速处理数据流的 p i c i j 日，s 即- s p r i n t 并行算法，便于由硬件加速实现。 3 东南大学硕士学位论文 1 3主要研究工作和内容安捧 以电力系统暂态稳定评估为需求背景与部署环境，本文主要围绕适用于数据流实时环境 下的数据流分类算法的改进，以及针对该算法的硬件实现进行研究，主要研究工作包括： 如何改进s 豫i n t 算法，使其进一步适合数据流的应用范围同时又能够方便硬件设计 如何快速，准确的判断分类过程中出现的概念漂移问题以及如何快速的重新调摧训 练窗口和待分类窗口( 在改进的算法基础上进行数据流硬分类器的框图设计) 本文将按照如下方式进行组织：第二章介绍数据流的电力应用背景以及数据流硬分类器 的逻辑框架设计( 包括数据流硬分类器的相关技术和最终的逻辑框架设计思路介绍) ，概要 描述数据流硬分类器平台的体系架构与功能模块划分以及一些数据流分类的基本概念；第三 章介绍了数据流硬分类器的概念漂移的定义，如何判定概念漂移的方法，分类器窗口大小的 动态调整策略以及对具体的相关算法流程，设计框图的设计思想，并最终提出了设计总体框 图；第四章介绍数据流硬分类器的分类算法设计，包括对传统的s p l l i g r 算法的介绍，并在 原算法基础上提出效率上的改进措施得到s e u - s p r i n t 算法，并进一步融入并行思想提出了 并行算法p a r a l l e l - - s f f j - s p r i n t 算法。第五章对本文的工作进行总结与展望 4 第二章数据流硬分类器框架设计概述 第二章数据流硬分类器框架设计概述 2 1电力应用背景知识介绍 电力系统是人民生活中的基础设施，电力系统的安全运行，可靠的供电直接关系到国家 各行业的发展，以及人民生活水平的提高电力系统是由发电厂、变电所、输电网，配电网 和用户的用电设备等组成，并由调度控制中心对全系统的运行进行统一的管理。电网监视和 控制的计算机信息系统是为电网运行管理服务的特殊的信息系统，简称为电网监控系统。它 是电力系统中一个功能比较专一的系统，同时也是一个不可缺少的现代化手段。 我们知道电力系统是典型的高维、非线性动态系统，其暂态稳定评估可看作有限样本下 的模式识别问题。 电力系统大致有1 8 维特征向量，具体含义如下表所示： 表2 - 1 电力系统特征向量表 x l系统总负荷x 7切除瞬时发电机角 x 1 3励磁增益 度 工2 部分节点负荷 x 8 故障瞬时发电机动 x 1 4故障瞬间发电机 能加速功率 x 3 系统母线电压平均值 x 9 切除瞬时c o i 相角变 x 1 5故障瞬间c o i 加 化速度 x 4 故障位置 x l o系统总发电量x 1 6切除瞬时发电机 加速度 x 5故障瞬间发电机加速度x l l部分母线电压 x 1 7切除瞬时发电机 动能 x 6最大加速度发电机初始 x 1 2母线电压最大最小x 1 8系统总调整能量 角值 稳定程度y i 划分的方法是，根据各样本极限切除时间t c c t ( 单位为周波) 的不同，描述 暂态稳定程度的一维向量y i 的取值范围为 1 ，2 ，3 ，其中，1 表示系统不稳定( t c c t s 5 ) ； 2 表示系统临界稳定( 5 s t c c t 1 0 ) ；3 表示系统稳定( 1 0 s t c c t 1 5 ) 图2 - 1 电力监控系统框架 图2 - 1 中的信息处理模块的具体结构如图2 吨所示： 5 东南大学硕士学位论文 图2 - 2 信息处理模块 图2 - 2 中灰色的表示控制模块和控制流程，白色的表示数据 其中图z _ 2 中数据流套询模块采用的是s e u s t r f 瑚i 体系结构，具体如图2 3 所示： 图2 - 3 数据流查询模块体系结构 为了能够快速及时地处理高逮数据流，对数据流采用专门硬件进行颈处理是一个报好 的选择。基于硬件预处理数据流管理系统s e u s t r e a m 并不仅仅依靠查询优化、系统调 用等传统手段来提高数据流的处理速度，而是考虑一种全新的体系结构来达到目的。 基于硬件预处理的数据流管理系统分为两部份：前端预处理器朝后端数据引擎前端 预处理器主要负责对进入系统的数据流进行预处理，主要是通过系统矮靖传送来的控制命 6 第二章数据流硬分类器框架设计概述 令进行状态初始化，对数据流数据进行滤波、数据压缩和数据加标记处理。前端预处理器 采用软硬件协同的方式以提高数据处理速度。经过前端处理之后的数据通过网络传往后端， 经过数据流划分控制器，在并行调度器的控制下，根据用户查询请求得出的调度策略动态 划分数据流元组，在并行查询执行器的控制下由各自的处理器并行地完成查询处理 在系统后端的数据引擎端，带有时间参数的连续查询经过查询语法分析器系统后保存 在注册查询缓冲中，连续查询被解析和分解为多个操作算子，由并行调度器生成动态查询 计划，依照查询计划执行策略将某些操作算子组成查询因子，经过查询输出控制器下载到 前端硬件查询处理模块 系统后端的数据引擎主要负责连续查询的语法分析、并行查询计划生成、将预处理过 的元组划分到不同的数据缓存，对并行处理得到的查询结果的进行最后组装分发及负载均 衡和服务质量监控等功能。系统前端的查询预处理层接收并行数据引擎的查询请求，对多 路采集来的模拟量或开关量进行本地预处理或部分计算，形成分布式处查询代理，将预处 理结果送交至后端查询引擎 而我们所研究的分类器就在数据流分析模块中，也就是在所谓的数据挖掘模块中。 其中分类器是用来对电力系统进行暂态稳定评估用的 具体的分类器的功能框架将在后续篇章里面陆续提及 2 2硬件相关设计工具以及工业基本设计流程介绍 2 2 1e d a 技术及其发展 现代电子设计技术的核心是e d a 技术。e d a 技术就是依赖功能强大的计算机，在e d a 工具软件平台上，对以硬件描述语言h d l 为系统逻辑描述手段完成的设计文件，自动的完 成逻辑编译，逻辑化简，逻辑分割，逻辑综合，结构综合( 布局布线) ，以及逻辑优化和 仿真测试，直至实现既定的电子线路系统功能e d a 技术使得设计者的工作仅限于利用软 件的方式，也就是利用硬件描述语言和e d a 软件来完成对系统硬件功能的实现 e d a 技术在硬件实现方面融合了大规模集成电路制造技术，i c 版图设计技术， s i c 测 试和封装技术，f p g a c p l d 编程下载技术，自动测试技术等；在计算机辅助工程方面融合 了计算机辅助设计( c 柚) ，计算机辅助制造( c 棚) ，计算机辅助测试( c a t ) 计算机辅助 工程( c e ) 技术以及多种计算机语言的设计概念；而在现代电子学方面则容纳了更多的内 容，如电子线路设计理论，数字信号处理技术，数字系统建模和优化技术以及长线技术理 论等等 e d a 技术的发展大致分为三个阶段； 2 0 世纪7 0 年代，集成电路制作方面m o si 艺已得到广泛的应用。可编程逻辑技术以 及其器件已经问世，计算机作为一种运算工具已在科研领域得到广泛应用。而在后期，c a d 的概念已见雏形。这一阶段人们开始利用计算机取代手工劳动，辅助进行集成电路版图编 辑，p c b 布局布线等工作。 2 0 世纪8 0 年代，集成电路设计进入了c m o s ( 互补场效应管) 时代。复杂可编程逻辑 器件已进入商业应用，相应的辅助设计软件也已投入使用而在8 0 年代末，出现了f p g a ( f i e l dp r o g r a m a b l eg a t ea r r a y ) ，c a e 和c a d 技术的应用更为广泛，它们在p c b 设计 方面的原理图输入，自动布局布线以及p c b 分析，以及逻辑设计，逻辑仿真，布尔方程综 合和化简等为电子设计自动化必须解决的电路建模，标准文档以及仿真测试奠定了基础。 进入2 0 世纪9 0 年代，随着硬件描述语言的标准化得到进一步的确认。计算机辅助工 程。辅助分析和辅助设计在电子技术领域获得更加广泛的应用，与此同时电子技术在通信， 计算机以及家电产品生产中的市场需求和技术需求，极大地推动了全新的电子设计自动化 技术的应用和发展。特别是集成电路设计工艺步入了超深亚微米阶段，百万门以上的大规 7 东南大学硕士学位论文 模可编程逻辑器件的陆续面世，以及基于计算机技术的面向用户的低成本大规模a s i c 设计 技术的应用，促进了e d 技术的形成更为重要的是各e d a 公司致力于推出兼容各种硬件 实现方案和支持标准硬件描述语言的e d a 工具软件的研究，都有效地将e d a 技术推向成熟 e d a 技术在进入2 1 世纪后得到了又很大的发展，突出表现在以下几个方面： 使电子设计成果以自主知识产权的方式得以明确表达和确认成为可能 在仿真和设计两方面支持标准硬件描述语言的功能强大的e d a 软件不断推出 电子技术全方位纳入e d a 领域，除了日益成熟的数字技术外，传统的电路系统设 计建模理念发生了重大的变化：软件无线电技术的崛起，模拟电路系统硬件描述 语言的表达和设计的标准化，系统可编程模拟器件的出现。数字信号处理和图像 处理的全硬件实现方案的普遍接受，软硬件技术的进一步融合等。 e d a 使得电子领域各学科的界限更加模糊，更加互为包容：模拟和数字，软件与 硬件，系统与器件，a s i c 与f p g a ，行为与结构等 更大规模的f p g a 和c p l d 器件的不断推出 基于e d a 工具的a s i c 设计标准单元已涵盖大规模电子系统以及i p 核模块。 软硬件i p 核在电子行业的产业领域，技术领域和设计应用领域得到进一步确认 ( i p 也就是i n t e l l e c t u a lp r o p e r t y ，即知识产权的简称，往往指一个公司出售给 另一个公司的硬件设计包) 2 2 2e d a 技术设计方法以及流程 一般的，利用e d a 技术进行电子系统设计，最后的目标是完成专用集成电路a s i c 的设计和实现，a s i c 作为最终的物理平台，集中容纳了用户通过e d 技术将电子应用 系统的既定功能和技术指标具体实现的硬件实体一般而言，专用集成电路就是具有 专门用途和特定功能的独立集成电路器件，根据这个定义，作为e d a 技术最终实现目 标的 s i c ，可以通过三种途径来完成 。 1 ) 超大规模可编程逻辑器件 f p g a 和c p l d 是实现这一途径的主流器件，它们的特点是直接面向用户，具有极 大的灵活性和通用性，使用方便，硬件测试和实现快捷，开发效率高，成本低，上市 时间短，技术维护简单，工作可靠性好等。f p g a 和c p l d 的应用是e d a 技术有机融合 软硬件电子设计技术，s o c 和a s i c 设计，以及对自动化设计与自动实现最典型的诠释。 由于f p g 和c p l d 的开发工具，开发流程和使用方法与& s i c 有类似之处，因此这类器 件通常也被称为可编程专用i c ，或可编程a s i c 2 ) 半定制或全定制a s i c 基于e d a 设计技术的半定制或全定制a s i c ，根据它们的实现工艺，可统称为掩模 a s i c 或直接称& s i c ，可编程a s i c 与掩模& s i c 相比，不同之处在于前者具有面向用户 的灵活多样的可编程性。 3 ) 混合 s i c 混合a s i c 主要指既具有面向用户的f p g a 可编程功能和逻辑资源，同时也含有可 方便调用和配置的硬件标准单元模块，如c p u ，r a m ，r o w ，硬件加法器，乘法器等。x i l i n x 和a l t e r a 公司已经推出了这方面的器件，如v i r t e x - - l i p r o 系列和s t r a t i x 系列等。 混合a s i c 为s o c 和s o p c ( s y s t e m0 1 1ap r o g r a m m a b l ec h i p ) 的设计实现成为便捷的途 径。 下面我们简单介绍下基于h i ) l 语言的f p g a 设计流程，具体如图2 - 4 所示： b 第二章数据流硬分类器框架设计概述 图2 - 4f p g a 系统设计流程图 1 ) 电路设计与输入 电路设计与输入是指通过某些规范的描述方式，将工程师电路构思输入给e d a 工具 常用的设计输入方法有硬件描述语言( 肋l ) 和原理图设计方法等目前进行大型工程设计 时，最常用得设计方法是h d l 设计输入法，其中影响最为广泛的i l d l 语言是v h d l 和v e r i l o g i i d l 。它们的共同特点是利于由顶向下设计，利于模块的划分与复用，可移植性好，通用性 好，设计不因芯片的工艺与结构的不同而变化，更利于向a s i c 的移植。波形输入和状态机 输入方法是两种常用的辅助设计输入方法：使用波形输入法时，只要绘制出激励波形和输 出波形。e d a 软件就能自动地根据响应关系进行设计；使用状态机输入法时，设计者只需 画出状态转移图，e d a 软件就能生成相应的h d l 代码或者原理图，使用十分方便。但是需 要指出的是，波形输入和状态机输入方法只能在某些特殊情况下缓解设计者的工作量，并 不适合所有的设计 2 ) 功能仿真 电路设计完成后，要用专用的仿真器对设计进行功能仿真，验证电路功能是否符合设 计要求功能仿真有时又被称为前仿真，通过仿真能及时发现设计中的错误，加快设计进 9 东南大学硕士学位论文 度，提高设计的可靠性 3 ) 逻辑综合 逻辑综合是将皿l 语言，原理图等设计输入翻译成由与，或。非门，r a m ，触发器等基 本逻辑单元组成的逻辑连接( 即所谓的网表) 并根据目标与要求( 约束条件) 优化所生 成的逻辑连接，输出e d f 和e d n 等标准格式的网表文件，供f p g a c p l d 厂家的布局布线器 进行实现 4 ) 前仿真 前仿真就是所谓的综合后仿真，综合完成后需要检查综合结果是否与原设计一致，傲 综合后仿真在仿真时，把综合生成的标准延时文件反标注到综合仿真模型中去，可估计 门延时带来的影响。综合后仿真虽然比功能仿真精确一些，但是只能估计门延时，不能估 计线延时。仿真结果与布线后的实际情况还有一定的差距，并不一定十分准确。这种仿真 的目的在于检查综合器的综合结果是否与设计输入一致。目前主流综合工具日益成熟，对 于一般性设计，如果设计者确信自己表述明确，则可以省略综合后仿真步骤。但是如果在 布局布线后仿真时发现有电路结构与设计意图不符的现象，则常常需要回溯到综合后仿真 以确认是否是由于综合歧义造成的问题 5 ) 布局布线 综合结果的本质是一些由与，或，非门，触发器，r a m 等基本逻辑单元组成的逻辑网 表，它与芯片实际的配置情况还有较大差距此时应该使用f p g a c p l i ) 厂商提供的软件工 具，根据所选芯片的型号，将综合输出的逻辑网表适配到具体f p g c p id 器件上，这个过 程就叫实现过程因为只有器件开发商最了解器件的内部结构，所以实现步骤必须选用器 件开发商提供的工具在实现过程中最主要的过程是布局布线，所谓布局就是指将逻辑网 表中的硬件原语或者底层单元合理地适配到f p 6 a 内部的固有硬件结构上，布局的优劣对设 计的最终实现结果( 速度和面积) 影响很大；所谓布线是根据布局的拓扑结构，利用f p g a 内部的各种连线资源，合理正确连接各个元件的过程。f p 6 a 的结构相对复杂，为了获得更 好的实现结果，特别是保证能够满足设计的时序条件，一般采用时序驱动的引擎进行布局 布线，所以对于不同的设计输入，特别是不同的时序约束，获得的布局布线结果一般有较 大差异。c p l d 结构相对简单的多，其资源有限而且布线资源一般为交叉连接矩阵，故c p l d 的布局布线过程相对简单明朗得多，一般被称为适配过程一般情况下，用户可以通过设 置参数指定布局布线得优化准则。总的来说优化且标主要有两个方面，面积和速度。一般 根据设计得主要矛盾，选择面积或者速度或者平衡两者等优化目标，但是当两者冲突时， 一般满足时序约束要求更重要一些，此时选择速度或时序优化目标效果更佳 6 ) 后仿真以及时序仿真 将布局布线的时延信息反标注到设计网表中，所进行的仿真就叫时序仿真或布局布线 后仿真，简称后仿真布局布线之后生成的仿真时延文件包含的时延信息最全，不仅包含 门延时，还包含实际布线延迟，所以布线后仿真最准确，能较好地反映芯片的实际工作情 况。一般来说，布线后仿真步骤必须进行，通过布局布线后仿真能检查设计时序与f l e a 实际运行情况是否一致，确保设讦的可靠性和稳定性。布局布线后仿真的主要目的在于发 现时序违规，即不满足时序约束条件或者器件固有时序规则( 建立时间，保持时间等) 的 情况。在功能仿真中介绍的仿真工具一般都支持布局布线后仿真功能。当然，有时为了保 证设计的可靠性，在时序仿真后还要做一些验证 7 ) 在系统测试 设计开发的最后阶段就是在线调试或者将生成的配置文件写入芯片中进行测试。示波 器和逻辑分析仪是逻辑设计的主要调试工具。传统的逻辑功能板级验证手段是用逻辑分析 仪分析信号，设计时要求f f 6 a 和p c b 设计人员保留一定数量f i ) ( ；a 管脚作为测试管脚，编 1 0 第二章数据流硬分类器框架设计概述 写f l e a 代码时将需要观察的信号作为模块的输出信号，在综合实现时再把这些输出信号镇 定到测试管脚上，然后连接逻辑分析仪的探头到这些测试脚，设定触发条件，进行观测。 逻辑分析仪的特点是专业，高速，触发逻辑可以相对复杂。缺点是价格昂贵，灵活性差。 p c b 布线后测试脚的数量就固定了，不能灵活增加，当测试脚不够用时影响测试，如果测 试脚太多又影响p c b 布局布线对于相对简单一些的设计，我们可以使用一些f p g 在线片 内信号分析工具，它的主要功能是通过, t a g 口，在线，实时地读出f l e a 内部信号任何 仿真或验证步骤出现问题，就需要根据错误定位返回到相应的步骤更改或者重新设计 2 3数据流硬分类器的相关技术 2 3 1 基本概念 数据流：一系列连续且有序的点组成的序列x l ，“，x l 称为数据流：按照固 定的次序，这些点只能被读取一次或者几次 按照参照物和表示方式的不同，数据流又可以有很多种不同的数据流模式，一般有三 种常见的数据流模式。 赣撼禳陵蓥 d a t a s t r e a m 图2 _ 5 数据流示意图 数据流模型如图2 5 ，其中t 表示任一时间戳，a t 表示在该时间戳到达的数据，数据 流可以表示为 a “，8 t ，巩 在数据流模型中，处理的数据不再是从磁盘和内存 中随机访问读取的数据，而是一个或多个连续的、无穷的数据项组成的序列 。 数据流模型可分为以下3 类： 1 ) 时间序列数据流( 砌”& r e s 腻o d e 0 用来描述时问序列数据，如每分钟纳斯达克( n a s d a q ) 成交量。这个里面的t 时刻的 数据a t 就表示t 时刻实际到达的成交量数据。 如果用a 【t 】表示实际的t 时刻到达的数据量，那么在时间序列数据流中，有： a i f f i a t 成立； 2 ) 现金注册数据流( c a s hm 丽，口朋砘，) 。 这是一类应用普遍的模型，类似于现金记账一样，每次的数据识是t 1 时刻到t 时刻的 现金增量。如果用a i 【t 】表示流i 在t 时刻的现金到达总量，那么有： 牢| a 【t 】- a 【i 1 】成立； 十字转门数据流( t u r a s t 如m o d e l ) 。 这种模式得名自繁忙的地下铁路站上限制旅客进入和离开。每个数据项a t 表示对a i t 】 的更新，也就是说a i t - a t t - 1 】+ a t ( 其中a 。可正可负) 这种数据流模式要求单位时间内流入 和流出的数据量不必相同，是研究数据流最为通用的动态模式 前2 种流模型具有很好的实际意义，特别是时序数据流，而t u r n s t i l e 模型则具有较好的 理论价值。 样本：数据流中用于训练和分类的流数据信息单位，这样的信息单位至少要包含两个属 性，一个类标签属性，个分类属性。在静态数据集中，除了训练样本和测试样本，分类样 本中并不要求一定附带类标签属性，丽对于滑动窗口模式下的数据流，由于要将最近分类之 后的样本作为即将重建的下一个分类模型的训练样本，因此有了上面的这些约定 东南大学硕士学位论文 2 4 数据流硬分类器逻辑设计与架构概述 根据数据流的处理流程，可将数据流分类器的逻辑设计分成大致五个部分： 数据封装，数据预处理。处理后数据的概要生成，在线分类处理层和对外接口层。 具体逻辑框图如图2 _ 6 所示： 图撕数据流处理流程图 2 4 1 数据预处理层 分类预处理是数据流分类过程中必不可少的阶段，而且预处理结果的好坏、性能优劣直 接关系到分类的精度和处理速度。理想的流数据应该尽可能反映数据源信息特征，而实际应 用中得到的数据流都不可避免地和实际情况存在差异，如采集、感测、传输及编码等过程都 可能造成数据质量下降，导致分类数据的失真和畸变。在数据获取的过程中，在将不同的数 据源的数据进行集成以及在数据传输过程中由于一些非系统的误差( 如：收集数据的设备出 现故障，或者传输路线上出现的误差) 会不可避免地产生简单和复杂的错误。据统计，大型数 据集中的错误率一般在5 左右或者更高。因此需要有强大的工具能在大量的数据流中进行 自动的数据清洗。目前有关数据流清洗研究与应用的一个