图论算法理论、实现及应用.pdf
图论算法理论、实现及应用.pdf清华大学前言、图论研究及图论教学0图论( Graph Theory)是数学的一个分支,它以图为研究对象。图论中的图是由若干个给定的顶点、及若干条连接两个顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用顶点代表事物,用连接两个顶点的边表示相应两个事物间具有这种关系。这种图提供了一个很自然的数据结构,可以对自然科学和社会科学中许多领域的问题进行恰当的描述或建模,因此图论研究越来越得到这些领域的专家和学者的重视。图论最早的研究源于瑞士数学家莱昂哈德·欧拉( Leonhard euler,1707~1783),他在1736年成功地解决了哥尼斯堡(Kω nigsberg)七桥问题,从而开创了图论的研究。哥尼斯堡七桥问题。东普鲁士哥尼斯堡市(今俄罗斯加里宁格勒)有一条布格( Pregel)河,如图1白a)所示。布格河横贯哥尼斯堡城区,它有两条支流,在这两条支流之间夹着一块岛形地带,这里是城市的繁华地区。全城分为北、东、南、岛四个区,各区之间共有七座桥梁联系着。人们长期生活在河畔、岛上,来往于七桥之间。有人提出这样一个问题:能不能一次走遍所有的七座桥,而每座桥只准经过一次?问题提出后,很多人对此很感兴趣,纷纷进行试验,但在相当长的时间里,始终未能解决。(B)东(D)C南C)(a)(b)图1七桥问题欧拉在1736年解决了这个问题,他将这个问题抽象为一个图论问题:把每一块陆地用一个顶点来代替,将每一座桥用连接相应两个顶点的一条边来代替,从而得到一个图(如图1(b)所示)欧拉证明了这个问题没有解(详见本书5.1节),并且推广了这个问题,给出了“对于一个给定的图,能否用某种方式走遍所有的边、且没有重复”的判定法则。这项工作使欧拉成为图论及拓扑学的创始人。在此后的两百多年时间里,图论的研究从萌芽阶段,逐渐发展成为数学的一个新分支。特别是从20世纪初期开始,在生产管理、交通运输、计算机和通讯网络等方面涌现了许多离散性问题,这极大地促进了图论的发展。20世纪70年代以后,由于高性能计算机的出现,使大规模的图论问题的求解成为可能。现在,图论理论广泛应用在运筹学、计算机科学、电子学、信息论、控制论、网络理论、经济管理等领域。由于图论的重要性,越来越多的大学将图论单独作为一门课程来开设,把它作为数学、计算本文中关于图论课程教学改革的一些思想,已经发表在《计算机教育》2009年第20期上,论文题目为《计算机专业图论课程教学改革探索》,即参考文献[20获得《计算机教育》杂志社举办的“英特尔杯”20090年全国计算机教育优秀论文评比二等奖)。图论算法理论、实现及应用杋科学、电子学、管理学等专业本科生和硏究生的必修课或选修课。很多其他课程的内容也都涉及到图论知识,如离散数学、运筹学、拓扑学等。介绍图论理论的教材逐渐增多,其中也不乏优秀的教材,如文献[。这些课程和教材或者是侧重于完整的图论知识体系介绍、以及复杂的图论定理的数学证明,或者是侧重于从应用数学的角度研究图论在各领域的应用。另外,为了实现用计算杋程序求解各种应用问题,计算机科学家抽象岀许多数据结构,如栈队列、堆、树及二叉树、图等,其中图是最重要的数据结构之一,也是应用得最广的数据结构之。数据结构课程是专门硏究这些数据结枃的描述、实现及应用的课程。数据结构课程讲到图论部分时,侧重于图结构的描述、图结构的存储、少量基本的图论算法的实现等等许多学生(特别是计算机专业的学生)在学习图论时,都不满足于图论算法的手工和草稿纸演算,迫切地想知道如何用程序实现图论中的算法,以及如何将这些算法思想用来求解实际问题据作者调査统计,市面上侧重于用程序实现图论算法、并通过例题阐述图论算法思想及其应用的教材少之又少。本教材希望能弥补这一缺憾。所以本书立足于图论算法理论和思想的描述及程序实现,并以大量的 ACM/ICPC竞赛题目来阐述图论算法思想在求解这些题目中的应用。接下来简要地介绍 ACMICPC程序设计竞赛。、 ACM/ICPC程序设计竞赛1.ACMIICPCACM/ICPO( ACM International Collegiate Programming Contest,国际大学生程序设计竞赛)是由美国计算机协会ACM( Association for Computing Machinery)主办的,世界上公认的规模最大、水平最高的国际大学生程序设计竞赛,其目的旨在使大学生运用计算机来充分展示自己分析问题和解决问题的能力。该项竞赛从1977年第一次举办世界总决赛以来,至今已连续举办30多届了。该项竞赛一直受到国际各知名大学的重视,并受到全世界各著名计算机公司的高度关注。ACM/ICPC竞赛分区域预赛和总决赛两个阶段进行,各预赛区第一名自动获得参加世界总决赛的资格。世界总决赛安排在每年的3~4月举行,而区域预赛安排在上一年的9~12月在各大洲举行。ACMICPC竞赛以组队方式进行比赛,每支队伍由不超过3名队员组成,比赛时每支队伍只能使用一台计算机。在5个小时的比赛时间里,参赛队伍要解答610道指定的题目。排名时,首先根据解题数目来排名,如果多支队伍解题数量相同,则根据队伍的总用时进行排名(用时越少,排名越靠前)。每支队伍的总用时为每道解答正确的题目的用时总和。每道解答正确的题目的用时为从比赛开始计时到该题目解答被判定为正确的时间,其间每一次错误的提交运行将被加罚20分钟时间。最终未正确解答的题目不记入总时间,其提交也不加罚时间。ACMICPC竞赛在公平竞争的前提下,提供了一个让大学生充分展示用计算机解决问题的能力与才华的平台。 ACMICPC竞赛鼓励创造性和团队协作精神,鼓励在编写程序时的开拓与创新,它考验参赛选手在承受相当大的压力下所表现出来的非凡能力。竞赛所触发的大学生的竞争意识为加速培养计算机人才提供了最好的动力。竞赛中对解决问题的苛刻要求和标准使得大学生对解决问题的深度和广度展开最大程度的追求,也为计算机科学的研究和发展作了一个最好的导向。2.在线评判网站随着 ACMICPC程序设计竞赛的推广,各种程序在线评判( Online judge,简写为OJ)网站也应运而生,这为程序设计爱好者提供了一种新的程序实践方法:在线程序实践。①作者对互动出版网站(www.china-pub.com)和卓越亚马逊网站(www.amazon.cn)上列出的全部图论相关书目及目录进行了仔细的分析,从而得出的结论在线程序实践是指由OJ网站提供题目,用户在线提交程序,OJ网站的在线评判系统实时评判并反馈评判结果。这些题目一般具有较强的趣味性和挑战性,评判过程和结果也公正及时,因此能引起用户的极大兴趣。用户在解题时编写的解答程序通过网页提交给在线评判系统称为提交运行,每一次提交运行会被判为正确或者错误,判决结果会及时显示在网页上用户从评判系统收到的反馈信息包括:" Accepted程序通过评判!Compile error"—程序编译出错。" Time limit exceeded"—程序运行超过该题的时间上限还没有得到输出结果。" Memory Limit Exceeded-内存使用量超过题目里规定的上限。"outpυ ut Limit exceeded"—输出数据量过大(可能是因为陷入死循环了)。" Presentation error"—输出格式不对,可检査空格、空行等等细节。" Run Time error"—程序运行过程中出现非正常中断,如数组越界等。Wrong Answer"—用户程序的输出错误。等等。用户可以根据OJ系统反馈回来的评判结果反复修改程序,直到最终收获 Accept(程序正确)。这个过程不仅能培养用户独立分析问题、解决问题的能力,而且每成功解决一道题目都能给用户带来极大的成就感。、本书安排本书共分9章,每章内容安排如下:第1章介绍图论的一些基本概念,以及图的两种重要存储表示方法:邻接矩阵和邻接表,并初步讨论了存储方式对图论算法复杂度的影响。第2章讨论了图的遍历,遍历是很多图论算法的基础。本章介绍了两种重要的遍历方法:深度优先搜索和广度优先搜索,并对这两种遍历算法的思想、程序实现、算法复杂度作了详细的分析和讨论。本章还讨论了活动网络,包括AOV网络与拓扑排序问题、AOE网络和关键路径问题。第3章讨论树与生成树问题,主要介绍求无向连通图最小生成树的三个算法:克鲁斯卡尔( Kruskal)算法、 boruvka算法和普里姆(Prin)算法,并对这三个算法的思想、程序实现、算法复杂度作了详细的分析和讨论。另外,本章还讨论了判断生成树是否唯一的方法。第4章讨论了有向网(或无向网)中一个典型的问题:最短路径问题。本章介绍了求解最短路径问题的4个算法:Dsa算法、 Bellman-FoH算法、SPH算法和Fod算法,这4个算法分别适用于有向网(或无向网)中各边权值的取值的不同情形及问题求解的不同需要。本章着重对这4个算法的思想、递推过程、算法复杂度作了详细的讨论,并对这4个算法作了详细的对比分析。本章还介绍了求最短路径的算法思想在求解差分约束系统中的应用。第5章讨论了可行遍性问题,包括欧拉回路、汉密尔顿回路以及中国邮递员问题。前两个概念容易混淆,欧拉回路要求经过每条边一次且仅一次并回到出发点,而汉密尔顿回路要求经过每个顶点一次且仅一次并回到出发点。本章介绍这相关概念及定理,并讨论这两种回路及中国邮递员问题的求解方法和应用。第6章讨论了网络流问题。许多系统包含了流量问题,例如,公路系统中有车辆流,控制系统中有信息流,供水系统中有水流,金融系统中有现金流等等。从问题求解的需求出发,网络流问题可以分为:网络最大流,流量有上下界的网络的最大流和最小流,最小费用最大流,流量有图论算法理论、实现及应用上下界的网络的最小费用最大流等。本章介绍各种网络流问题的求解方法。第7章讨论了点支配集、点覆盖集、点独立集、边覆盖集、边独立集(匹配),这些概念之间存在一定的联系,也容易混淆。本章主要讨论了各种匹配问题,以及求解二部图最大匹配的算法程序实现和应用。第8章讨论图的连通性,这是图论中一个重要的概念。本章介绍了无向连通图和非连通图无向图的点连通性(包括割顶集、割点、顶点连通度、点双连通图等)、边连通性(包括割边集、割边、边连通度、边双连通图等)、有向图的强连通性(包括强连通、弱连通和单连通)。本章着重介绍上述概念及求解算法。第9章讨论平面图和着色问题。本章介绍了平面图和非平面图的概念、平面图的判定方法,以及图的顶点着色、边着色、平面图的面着色等概念和求解算法。四、本书读者对象及本书特点本书的读者对象为计算机专业学生或对 ACM/ICPC竞赛感兴趣的学生,可以作为高等院校计算机(或相关专业)的图论等相关课程的主教材,也可作为 ACMICPO竞赛的辅导教材。学生或读者应该具备CC艹语言知识,已经掌握了一定的程序设计思想和方法,具备一定的算法分析与设计能力,并能熟练使用数据结构。本书在内容取材、描述上具有如下特点。1)许多图论教材对图论概念的描述不一致,造成读者的阅读困难,本书试图改变这一现状。在每个概念的表述上作者査阅了大量的图论著作并进行比较分析。在本书中,作者对每个概念采用大多数图论教材采用(或约定)的名词、定义方法等。2)本书对图论算法思想的描述尽可能采用浅显易懂的语言来描述。3)本书忽略所有图论定理的证明,着重分析图论算法的思想,重点在于这些图论算法的程序实现。对图论算法的程序实现是以 ACMICPC例题来阐述的。上下两册书共收录了130余道ACMICPC竞赛题目,例题和练习题各约占一半。本书附录列出了本书所有例题和练习题在ZOJ、POJ及UVA上的题号。4)本书图表内容丰富。全书共绘制了270余幅图表,为此在目录后专门列出了本书的图录5)为方便读者阅读和使用,作者对本书中出现的图论术语、符号、图论算法及应用分别作了索引,列在本书后面五、致谢本书收录了130余道 ACMICPC竞赛题目,这些题目在阐述图论算法思想、演示图论算法应用等方面起着重要的作用,部分例题的解答程序也参考了网络上发布的一些源代码。同时,本书在编写过程中还参考了国内外多本优秀的图论教材(详见参考文献)。在此,编者对这些题目、源代码和图论教材的作者一并表示忠心的谢意。本书的编写和岀版得到了2010年浙江省教育科学规划研究课题“以大学生学科竞赛为契机推动课程群的规划与建设”(编号:SCG156)的支持,在此表示感谢。另外,本书的岀版得到了北京大学出版社的大力支持,在此表示衷心的感谢。由于作者水平有限,在编写本书时难免出错,欢迎读者指正,或者读者有什么好的建议,都可以联系编者:wguiping@163.com。不胜感激!!!编者2010年1月目录第1章图的基本概念及图的存储3.1.1树11基本概念1113.1.2森林5551.1.1有向图与无向图32生成树及最小生成树1.1.2完全图、稀疏图、稠密图321生成树1.1.3顶点与顶点、顶点与边的关系…3322最小生成树1.14顶点的度数及度序列33克鲁斯卡尔()算法1.1.5二部图与完全二部图3.3.1算法思想116图的同构332等价类与并查集1.17子图与生成树3.3.3 Kruskal算法实现118路径56778993.34Boruvka.951.19连通性3.35例题解析1.1.10权值、有向网与无向网34普里姆(Pim)算法图的存储表示341Prim算法思想106121邻接矩阵……342Prim算法实现1071.2.2邻接表15343关于普里姆算法的进一步讨论.11012.3关于邻接矩阵和邻接表的进一步344例题解析111讨论5判定最小生成树是否唯120第2章图的遍历与活动网络问题3.5.1最小生成树不唯一的原因分析.1202.1DFS遍历3.52判定最小生成树是否唯一的方法12122.1DFS算法思想4443.53例题解析212DFS算法的实现及复杂度分析……25第4章最短路径问题1272.1.3例题解析284.1边上权值非负情形的单源最短路径问题22BFS遍历Dijkstra算法12722.1BFS算法思想4.1.1算法思想12722.2BFS算法的实现及复杂度分析…414.1.2算法实现1292.2.3关于DFS算法和BFS算法的说明.434.1.3关于 Dijkstra算法的进一步讨论.1322.2.4例题解析.…434.14例题解析13323活动网络一AOV网络614.2边上权值为任意值的单源最短路径问题2.3.1AOV网络与拓扑排序61一 Bellman-Ford算法…1432.3.2拓扑排序实现方法42.1算法思想1432.3.3关于拓扑排序的进一步说明….6742.2算法实现1452.34例题解析42.3关于 Bellman-Ford算法的进一步24活动网络一AOE网络78讨论1482.4.1AOE网络与关键路径4.24例题解析2.42关键路径求解方法794.3 Bellman-Ford算法的改进一SPFA算法.161第3章树与图的生成树4.3.1算法思想….163.1树与森林…4.32算法实现图论算法理论、实现及应用4.3.3关于SPFA算法的进一步讨论…16564.1基本概念3244.34例题解析……166642最小费用最大流算法32544所有顶点之间的最短路径一Foyd算法…175644例题解析3274.4.1算法思想176第7章支配集、覆盖集、独立集与匹配3404.42算法实现…1777.1点支配集、点覆盖集、点独立集34044.3关于Foyd算法的进一步分析….1807.1.1点支配集3404.44例题解析1807.1.2点覆盖集3414.5差分约束系统7.1.3点独立集4.5.1差分约東系统与最短路径7.1.4点支配集、点覆盖集、点独立集4.52例题解析之间的联系第5章可行遍性问题2087.2点支配集、点覆盖集、点独立集的求解.34551欧拉回路2087.2.1逻辑运算34551.1基本概念及定理2087.22极小点支配集的求解34551.2欧拉回路的判定2117.2.3极小点覆盖集、极大点独立集的52欧拉回路的求解219求解52.1DFS搜索求解欧拉回路21973边覆盖集与边独立集.347522 Fleury(佛罗莱)算法.7.3.1边覆盖集….34753中国邮递员问题2337.32边独立集(匹配)54汉密尔顿回路2347.3.3最大边独立集(最大匹配)与最541基本概念及定理235小边覆盖集之间的联系5.42汉密尔顿回路求解74匹配问题350第6章网络流问题242741完美匹配3516.1网络最大流242742二部图的完备匹配与完美匹配..35161.1基本概念24274.3最佳匹配3526.1.2最大流最小割定理2477.44匹配问题求解的基本概念及思路3526.1.3网络最大流的求解2487.5二部图最大匹配问题的求解3536.1.4般增广路方法7.5.1网络流解法353Ford- Fulkerson算法2487.42匈牙利算法3556.1.5最短增广路算法2567.4.3例题解析6.16连续最短增广路算法- Dinic算法260第8章图的连通性问题.380617一般预流推进算法2628.1基本概念3806.1.8最高标号预流推进算法26581.1连通图与非连通图.3806.1.9网络最大流算法总结2668.1.2无向图的点连通性3816.1.10例题解析2668.1.3无向图的边连通性38262最小割的求解8.14无向图顶点连通性和边连通性的6.3流量有上下界的网络的最大流和最小流.300联系3846.3.1流量有上下界的容量网络8.1.5有向图的连通性6.3.2流量有上下界的网络的最大流.30382无向图点连通性的求解及应用6.3.3流量有上下界的网络的最小流.3048.21关节点的求解6.34例题解析310322重连通分量的求解64最小费用最大流323顶点连通度的求解2目录83无向图边连通性的求解及应用40192.1欧拉公式440831割边的求解401922欧拉公式的应用4418.32边双连通分量的求解4059.3平面图的判定445833边连通度的求解41294图的着色问题44684有向图强连通性的求解及应用416941地图染色与四色猜想4468.41有向图强连通分量的求解算法416942图的着色447842有向图强连通分量的应用418943图着色的应用449第9章平面图及图的着色问题4379.44图着色求解算法及例题解析…..4509.1基本概念…437索引91.1平面图与非平面图437、图论术语索引91.2区域与边界、符号索引4599.1.3极大平面图与极小非平面图.…438、图论问题及算法索引….46914平面图的对偶图439附录本书例题和练习题目录…91.5关于平面图的一些定理439参考文献92欧拉公式及其应用440
- 2020-12-08下载
- 积分：1
altera公司IP核使用手册.PDF
altera公司IP核使用手册,对于学习EDA技术的学生或工程师有用A吉RAContentsChapter 1. About this MegaCore FunctionRelease informat1-1Device Family Support···Introduction.··········FeaturesOpen core plus evaluation1-3Performance···Chapter 2. Getting StartedDesign Flow衡·鲁·,看·,音番2-1Megacore Function walkthrough2-2Create a New quartus II Pi2-2Launch the mega Wizard Plug-in ManagerStep 1: Parameterize2-5Step 2: Set Up SimulationStep 3: Generate..,2-11Simulate the design2-13Compile the design2-13Pa Device2-14Set Up Licensing2-15ppend the license to yourdat file2-15Specify the License File in the Quartus II Software...2-15Example Simulation and Compilation..2-16Example quartus Ii project2-16Example simulation with Test Vectors,,,,,,2-16Chapter 3. SpecificationsyperTransport Technology Overview1HT SyStems3-2HT Flow ControlHyper Transport MegaCore Function SpecificationPhysical InterfaceSynchronization and alignment ...Protocol interfClocking Options.......HyperTransport Mega Core Function Parameters and HT Link Performance3-10Signals3-14CSR Module...3-31OpenCore plus time-Out BehaviorAppendix A. ParametersIntroduction鲁鲁鲁A-1Parameter listsDevice Family and Read Only registers···········,,,,,,,,,,A-1Base Address Registers番鲁,A-2Clocking OptionsA-3Advanced settingso March 2009 Altera corporationHyperTransport MegaCore Function User GuideAppendix B. Stratix Device Pin AssignmentsIntroductionB-1GuidelinesAppendix C. Example designGeneral descriptionAdditional informationRevision historyInto-lHow to Contact alteraInfo-1Typographic Conventions ..........Info-2Hyper Transport MegaCore Function User Guideo March 2009 Altera CorporationA吉RA1. About this MegaCore FunctionRelease InformationTable 1-1 provides information about this release of the Hyper Transport Mega CoretfunctioTable 1-1. Hyper Transport Mega Core Function Release InformationitenlDescription∨ ersion9.0Release dateMarch 2009Ordering codeIP-HTProduct ID(s)0098Vendor iD(s)6AF7Altera verifies that the current version of the quartus@ll software compiles theprevious version of each MegaCore function. Any exceptions to this verification arereported in the Mega Core lP Library release Notes and Errata. Altera does not verifycompilation with Mega Core function versions older than one releaseDevice Family SupportMegaCore functions provide either full or preliminary support for target Alteradevice families:Full support means the Mega Core function meets all functional and timingrequirements for the device family and may be used in production designsa Preliminary support means the Mega Core function meets all functionalrequirements, but may still be undergoing timing analysis for the device family;itmay be used in production designs with cautionTable 1-2 shows the level of support offered by the Hyper Transport MegaCorefunction for each of the altera device familiesTable 1-2. Device Family SupportDevice FamilySupportHard Copy Stratix@FullStratixFulStratix IIFulStratix‖GXPreliminaryStratix GXOther device familiesNo supportC March 2009 Altera CorporationHyperT ransport Mega Core Function User Guide1-2Chapter 1: About this MegaCore FunctionIntroductionIntroductionThe Hyper Transport Mega Core function implements high-speed packet transfersbetween physical(PhY) and link-layer devices, and is fully compliant with theHyperTransport l/O Link Specification, Revision 1.03. This Mega Core function allowsdesigners to interface to a wide range of Hyper TransportTm technology(hT)enableddevices quickly and easily, including network processors, coprocessors, videochipsets, and ASICsFeaturesThe Hyper Transport Mega Core function has the following features8-bit fully integrated hT end-chain interfacePacket-based protocolDual unidirectional point-to-point linksUp to 16 Gigabits per second(Gbps)throughput(8 Gbps in each direction)200, 300, and 400 MHz DDR links in Stratix and Stratix GX devices200, 300, 400, and 500 MHz ddr links in Stratix II and Stratix II GX devicesLow-swing differential signaling with 100-Q2 differential impedanceHardware verified with Hyper fransport interfaces on multiple industry standardprocessor and bridge devicesFully parameterized mega core function allows flexible, easy configurationFully optimized for the altera stratix Il, Stratix, Stratix GX, and Stratix II GXevice famillesApplication-side interface uses the Altera AtlanticTM interface standardManages Hr flow control, optimizing performance and ease of useIndependent buffering for each HT virtual channelAutomatic handling of ht ordering rulesStalling of one virtual channel does not delay other virtual channels(subject toorderingFlexible parameterized buffer sizes, allowing customization depending onsystem requirementsUser interface has independent interfaces for the HT virtual channels, allowingindependent user logic designCyclic redundancy code(crc) generation and checking to preserve data integrityIntegrated detection and response to common HT error conditions■ CRC errorsEnd-chain errorsFully integrated HT configuration space includes all required configuration spaceregisters and HT capabilities list registersHyper Transport MegaCore Function User Guideo March 2009 Altera CorporationChapter 1: About this MegaCore FunctionPerformance32-bit and 64-bit support across all base address registers bars)automatically handles all csr space accessesVerilog HDL and VHdL simulation supportOpen Core Plus EvaluationWith the Altera free Open Core Plus evaluation feature, you can perform the followingSimulate the behavior of a mcgafunction(Altera MegaCore function or AMPPmegafunction) within your systema Verify the functionality of your design, as well as quickly and easily evaluate itssize and speedGenerate time-limited device programming files for designs that includeMegaCore functionsProgram a device and verify your design in hardwareYou only need to purchase a license for the Mega Core function when you arecompletely satisfied with its functionality and performance and want to take yourdesign to productiono For more information about Open Core Plus hardware evaluation using theHyperTransport MegaCore function, refer to"Open Core Plus Time-Out Behavior"onpage 3-40 and AN 320: Open Core Plus Evaluation of megafunctionsPerformanceThe Hyper Transport Mega Core function uses 20 differential I/O pin pairs and 2single-ended I/O pins, requiring 42 pins total. Table 1-3 through Table 1-5 showtypical performance and adaptive look-up table (alut) or logic element (LE)usagefor the HyperTransport MegaCore function in Stratix II GX, Stratix IL, Stratix, andStratix GX devices respectively, using the Quartus@ II software version 7.1Table 1-3 shows the maximum supported data rates in megabits per second(Mbps)by device family and speed gradeTable 1-3. Maximum Supported Hyper Transport Data Rates (Note 1)Speed GradeDevice Family-36Stratix ll GX devices 1000 Mbps 1000 Mbps 800 MbpsNA(2)N/A(2NA(2)Stratix devices1000 Mbps 1000 Mbps 800 Mbps N/A(2)NA(2)NA(2)Stratix devicesN/A(2N/A(2)00 Mbps 800 Mbps 600 Mbps400 MbpsFlip-Chip packagesStratix devicesNA(2)NA(2)NA(2)600 Mbps400 Mbps400 Mbps(Wire Bond packagesStratix GX devicesN/A(2) N/A(2)800 Mbps 800 Mbps 600 Mbps N/A(2)Notes to table 1-3(1)Rates are per interface bit. Multiply by eight to calculate the uni-directional data rate of an 8-bit inter face(2) Devices ot this speed grade are not ottered in this device familyC March 2009 Altera CorporationHyperTransport Mega Core Function User GuideChapter 1: About this MegaCore FunctionPerformanceTable 1-4 shows performance and device utilization for the Hyper TransportMegaCore function in Stratix II and Stratix II GX devicesTable 1-4. Hyper Transport Mega Core Function Performance in Stratix ll and Stratix ll GX DevicesParametersMemoryUserRXCombinationalHT Link InterfacePosted Non-Posted Response ClockingALUTSLogicfMAX(MHz) MAx(MHz)Buffers BuffersBuffers Option(12)Registers M4K M512 ( 3)3)Shared3.5005200120500125(4RX/TX/Ref35005200500Ref/x8Shared36005400160500>150RX/TXShared4.0006,00016150RX/TX16Shared4,1006,200500125(4)RX/TX/RefShared4.1006200500125(4Ref/TxShared4.2006400160150RX/TXNotes to table 1-4.Refer to " Clocking Options "on page 3-7 for more information about these options(2 )Other parameters(BAR configurations, etc. )vary the alut and Logic Register utilization numbers by approximately +/-200(3)Figures for -3 speed grade devices only(4) When using the Shared Rx/Tx/Ref and Shared Ref/Tx options, the user interface frequency is limited to exactly the ht frequency divided byTable 1-5 shows performance and device utilization for the Hyper TransportMegaCore function in Stratix and Stratix GX devicesTable 1-5. Hyper Transport Mega Core Function Performance in Stratix and Stratix GX DevicesUser Interface fmaxParametersUtilizationHT Link fMAX MHz)MHZ)RXRXSpeed GradePosted Non-Posted Response Clocking Option LEsM4KBuffers BuffersBuffers)(2 Blocks.5-66Shared rx/tx/ref1240010073)100734448888Shared Ref/Tx 7, 60014400400100{3)100(3)Shared rxtx7,90016400400>125>100Shared rxtx8.900125>100168Shared Rx/T×Ref9,400124004001003)100316Shared ref/ ix9.500144001003)10073)16Shared rx/x9.700400125Notes to table 1-5:(1)Refer to Clocking Options"on page 3-7 for more information about these options(2 )Other parameters( BAR configurations etc. )vary the LE utilization by approximately +/-200 LES(3 )When using the Shared Rx/Tx/ Ref and Shared Ref/Tx options, the user interface frequency is limited to exactly the hT frequency divided by fourHyper Transport MegaCore Function User GuideC March 2009 Altera CorporationA吉RA2. Getting StartedDesign FlowTo evaluate the HyperTransport Mega Core function using the Open Core Plus feature,include these steps in your design flowObtain and install the HyperTransport Mega Core functionThe HyperTransport Mega Core function is part of the MegaCore IP Library, which isdistributed with the Quartus ii software and downloadable from the altera websitewww.altera.como For system requirements and installation instructions, refer to Quartus II InstallationLicensing for Windows and Linux Workstations on the Altera website atwww.altera.com/literature/lit-qts.ispFigure 2-1 shows the directory structure after you install the HyperTransportMegaCore function, where is the installation directory. The default installationWindows is C: altera ; on Linux it islopt/alteraFigure 2-1. Directory StructureInstallation directorypContains the Altera MegaCore IP Library and third-party IP coresalteraContains the Altera MegaCore IP LibrarycommonContains shared componentshtContains the Hyper Transport Hyper Transport Megacore function files and documentationdocContains the documentation for the Hyper Transport MegaCore functionlibContains encrypted lower-level design filesexampleContains the design example for the Hyper Transport Mega Core function2. Create a custom variation of the Hyper Transport Mega Core function3. Implement the rest of your design using the design entry method of your choice4. Use the IP functional simulation model to verify the operation of your designo For more information about Ip functional simulation models, refer to the SimulatingAltera IP in Third-Party Simulation Tools chapter in volume 3 of the Quartus II Handbook5. Use the Quartus II software to compile your designC March 2009 Altera CorporationHyperT ransport Mega Core Function User Guide2-2Chapter 2: Getting StartedMega Core Function WalkthroughIg You can also generate an Open Core Plus time-limited programming file,which you can use to verify the operation of your design in hardware6. Purchase a license for the hypertransport Mega Core functionAfter you have purchased a license for the Hyper transport mega Core functionfollow these additional steps1. Set up licensing2. Generate a programming file for the Altera device(s)on your board3. Program the Altera device(s)with the completed designMegaCore Function WalkthroughThis walkthrough explains how to create a custom variation using the AlteraHyper Transport IP Toolbench and the Quartus II software, and simulate the functionusing an ip functional simulation model and the modelsim software when you arefinished generating your custom variation of the function, you can incorporate it intoⅴ our overall projectIe IP Toolbench allows you to select only legal combinations of parameters, and warnsou of any invalid configurationsIn this walkthrough you follow these stepsCreate a New Quartus II Projecta Launch the MegaWizard Plug-in Manager■Step1: Parameterizea Step 2: Set Up Simulation■Step3: Generate■ Simulate the designTo generate a wrapper file and Ip functional simulation model using default values,omit the procedure described in"Step 1: Parameterizeon page 2-5Create a New Quartus ll ProjectCreate a new Quartus II project with the New Project Wizard, which specifies theworking directory for the project, assigns the project name, and designates the nameof the top-level design entityTo create a new project, perform the following steps1. On the Windows Start menu, select Programs> Altera> Quartus II tostart the Quartus lI software. Alternatively, you can use the Quartus II Web editionsoftware2. In the Quartus II window, on the File menu, click New Project Wizard. If you didnot turn it off previously, the New Project Wizard Introduction page appears3. On the New Project Wizard Introduction page, click NextHyper Transport MegaCore Function User Guideo March 2009 Altera Corporation
- 2020-12-05下载
- 积分：1
