Nothing Special   »   [go: up one dir, main page]

CN113255269B - 一种性能驱动的多fpga雅克比模版计算最优部署方法及系统 - Google Patents

一种性能驱动的多fpga雅克比模版计算最优部署方法及系统 Download PDF

Info

Publication number
CN113255269B
CN113255269B CN202110528857.0A CN202110528857A CN113255269B CN 113255269 B CN113255269 B CN 113255269B CN 202110528857 A CN202110528857 A CN 202110528857A CN 113255269 B CN113255269 B CN 113255269B
Authority
CN
China
Prior art keywords
fpga
chip
hexagonal
jacobian
cost
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN202110528857.0A
Other languages
English (en)
Other versions
CN113255269A (zh
Inventor
伍卫国
王今雨
康益菲
冯雅琦
栗怡文
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Xian Jiaotong University
Original Assignee
Xian Jiaotong University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Xian Jiaotong University filed Critical Xian Jiaotong University
Priority to CN202110528857.0A priority Critical patent/CN113255269B/zh
Publication of CN113255269A publication Critical patent/CN113255269A/zh
Application granted granted Critical
Publication of CN113255269B publication Critical patent/CN113255269B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F30/00—Computer-aided design [CAD]
    • G06F30/30—Circuit design
    • G06F30/34—Circuit design for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2111/00—Details relating to CAD techniques
    • G06F2111/04—Constraint-based CAD
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2115/00—Details relating to the type of the circuit
    • G06F2115/02—System on chip [SoC] design

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Hardware Design (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Evolutionary Computation (AREA)
  • Geometry (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Stored Programmes (AREA)
  • Design And Manufacture Of Integrated Circuits (AREA)

Abstract

本发明公开了一种性能驱动的多FPGA雅克比模版计算最优部署方法及系统，对雅克比模版计算进行六边形分块，使分块间的数据能够并行运算；对运行雅克比模版计算的N种FPGA芯片进行形式化描述，使用数学表示不同FPGA芯片的各项属性；利用六边形分块和形式化描述内容进行数学建模，确定模型的约束条件，根据FPGA芯片模型的总成本、资源占用与总耗时确定目标函数；对雅克比六边形分块的属性、FPGA芯片形式化描述内容、各项约束条件与目标函数内容进行编写，生成模型文件后优化得到最优结果，利用最优结果实现最优放置策略。本发明实现模版计算在多FPGA芯片上的最优放置，有效节省FPGA芯片资源浪费，实现模版计算的高效运行，进而节省模版计算的工程开支。

Description

一种性能驱动的多FPGA雅克比模版计算最优部署方法及系统
技术领域
本发明属于电子技术领域，具体涉及一种性能驱动的多FPGA雅克比模版计算最优部署方法及系统。
背景技术
模版计算(Stencil Computation)是一种根据固定的“模版”形式迭代更新数组元素值的计算方式。作为流体动力学、电磁学等科学计算的模拟过程，是一种仿真计算的重要方法。根据应用场景和计算方式的不同，模版计算分为很多种，在众多模版计算类别中，雅克比(Jacobi)计算在线性方程组的求解领域具有广泛的研究和应用。
图1为1D Jacobi计算示意图，其中横轴为空间维度i，纵轴为时间维t，图中每一个实心黑点表示一个迭代实例(cell)，所有迭代实例组成了迭代空间。1D Jacobi由于空间维度为一维，所以其迭代空间为二维空间。箭头方向表示迭代实例之间的依赖关系，其中，箭头指向方向的迭代实例称为目标实例(target)，箭头发出方向的迭代实例称为源实例(source)。图2为对应的1D Jacobi计算的示例代码。
模版计算更新数据时采用的计算模版有很多种，其类型取决于所计算的应用领域，以图1为例，每一个迭代实例由其上一时间步(t-1)的三个迭代实例i、i+1和i-1计算得到。
模版计算的运算模式，是以上一时间步的结果作为当前时间步的输入进行计算，并且在同一时间步内没有数据依赖，因此，存在着大量的数据重用(data reuse)。这样的计算模式适合于并行计算来提高运行效率。
在高性能计算(High Performance Computing,HPC)时代，模版计算的运算载体主要以通用处理器芯片CPU为主，因为其采用的是冯·诺依曼架构，需要将待运算的cell加载至cache中进行运算，但是常见计算机的cache容量较小，很难存储所有时间步的迭代数据，因此需要与内存进行数据交换，而频繁的内存读取操作较为耗时，将影响模版计算的执行效率。
FPGA作为可编程硬件，拥有高效的并行性能，并且比CPU具有更高的能效比，是合适的模版计算运算平台，随着模版计算规模的日趋扩大、计算精度的不断提高，单一FPGA往往不能完成计算要求，多FPGA协同的模版计算加速模式成为主流。
目前以FPGA为平台的模版计算加速领域，缺少多个FPGA运行模版计算的相关研究，相比于单一芯片，多FPGA芯片需要考虑模版计算任务的划分、FPGA的选择与放置策略等问题。并且，根据逻辑电路天生并行性运算特点，需要设计芯片间数据的同步、一致性保证与验证机制，从而实现雅克比模版计算的高效能运行。
发明内容
本发明所要解决的技术问题在于针对上述现有技术中的不足，提供一种性能驱动的多FPGA雅克比模版计算最优部署方法及系统，提高雅克比模版计算的运行效率。
本发明采用以下技术方案：
一种性能驱动的多FPGA雅克比模版计算最优部署方法，包括以下步骤：
S1、对雅克比模版计算进行六边形分块，使分块间的数据能够并行运算；
S2、对运行雅克比模版计算的N种FPGA芯片进行形式化描述，使用数学表示不同FPGA芯片的各项属性；
S3、对步骤S1的六边形分块和步骤S2的形式化描述内容进行数学建模，确定模型的约束条件，根据FPGA芯片模型的总成本、资源占用与总耗时确定目标函数；
S4、利用步骤S1得到的雅克比六边形分块的属性、步骤S2得到的FPGA芯片形式化描述内容、步骤S3确定的各项约束条件与目标函数内容进行编写，生成模型文件后优化得到包括六边形分块的大小，FPGA芯片运行的六边形分块数量和顺序的最优结果，根据最优结果确定最优放置策略。
具体的，步骤S1中，定义六边形分块中任意一块六边形计算单元g如下：
g＝(ws,wl,h)
其中，ws为六边形分块的上下底宽度，wl为中心宽度，h为六边形分块的高，ws、wl和h均以cell数量计量。
具体的，步骤S2中，N种FPGA芯片的各项属性fn为：
其中，fren为芯片频率，为芯片各项资源数量，/>为片上带宽，/>为片间带宽，costn为芯片成本。
具体的，步骤S3中，首先定义雅克比模版计算放置策略的常量，然后定义雅克比模版计算放置策略的变量，对定义的常量和变量进行约束，确定六边形分块与所使用的FPGA芯片f所属关系唯一性约束、六边形分块的横向连续性约束、FPGA芯片型号唯一性约束、水平方向上起始与结束六边形分块参数约束、水平方向六边形分块数量约束、缓存数据容量约束和资源占用约束。
进一步的，六边形分块与所使用的FPGA芯片所属关系唯一性约束为：
六边形分块的横向连续性约束为：
FPGA芯片型号唯一性约束为：
水平方向上起始与结束六边形分块参数约束为：
wlast＝I-wfirst-x(ws+wl)
水平方向六边形分块数量约束为：
缓存数据容量约束
bufferleft＝h
buffertop＝ws
bufferright＝h
资源占用约束为：
其中，k∈K，F为所使用的FPGA芯片数量，ak,f为第k个六边形分块运行于第f个芯片，kl,km,kh为任意水平方向上的六边形分块，为六边形分块km与所运行的FPGA芯片f的所属关系，akl,f为六边形分块kl与所运行的FPGA芯片f的所属关系，/>为六边形分块kh与所运行的FPGA芯片f的所属关系，N为FPGA芯片种类，pf,n为第f个芯片的型号为n，wfirst为水平方向上第一个六边形分块的宽度，h为六边形分块的高，ws为六边形分块的上下底宽度，wl为六边形分块的中心宽度，wlast为水平方向上最后一个六边形分块的宽度，x为正整数，K为水平方向的六边形分块数量，bufferleft为六边形分块左侧需保存在缓存中的数据量，buffertop为六边形分块顶部需保存在缓存中的数据量，bufferright为六边形分块右侧需保存在缓存中的数据量，R为FPGA芯片资源种类，/>为运行在第f块FPGA所需的第r种资源数量，/>为第n种FPGA芯片的各类资源数量。
具体的，步骤S3中，目标函数为：
其中，Costsum为FPGA芯片的总成本，Costmax为FPGA芯片全部使用时的成本，Ressum为占用资源，Resmax为最大资源数量，Latencysum为通信总耗时，Latencymax为雅克比模版计算串行执行的耗时，w1,w2,w3为各项代价函数权值。
进一步的，使用FPGA芯片总成本Costsum如下：
所有可选FPGA芯片全部使用时的成本Costmax表示如下：
其中，F为所使用的FPGA芯片数量，N为FPGA芯片种类，costn为第n种FPGA芯片的成本，f为F中的一个变量，n为N中的一个变量，pf,n为第f个芯片的型号为n。
进一步的，所有使用的FPGA芯片占用的各项资源总和Ressum表示如下：
最大资源数量Resmax表示如下：
其中，F为所使用的FPGA芯片数量，N为FPGA芯片种类，为，f为F中的任意值，n为N中的任意值，/>为第n种FPGA芯片的各类资源数量。
进一步的，总耗时Latencysum表示如下：
h＝1时的总耗时的Latencymax表示如下：
Latencymax＝(latencycomm+latencycal)·T
其中，latencycomm为通信耗时，latencycal为运算耗时，T为雅克比模版计算迭代时间步数量，h为六边形分块的高。
本发明的另一技术方案是，一种性能驱动的多FPGA雅克比模版计算最优部署系统，包括：
分块模块，对雅克比模版计算进行六边形分块，使分块间的数据能够并行运算；
描述模块，对运行雅克比模版计算的N种FPGA芯片进行形式化描述，使用数学表示不同FPGA芯片的各项属性；
函数模块，对分块模块的六边形分块和描述模块的形式化描述内容进行数学建模，确定模型的约束条件，根据FPGA芯片模型的总成本、资源占用与总耗时确定目标函数；
放置模块，对分块模块得到的雅克比六边形分块的属性、描述模块得到的FPGA芯片形式化描述内容、函数模块确定的各项约束条件与目标函数内容进行编写，生成模型文件后优化得到包括六边形分块的大小，FPGA芯片运行的六边形分块数量和顺序的最优结果，根据最优结果确定最优放置策略。
与现有技术相比，本发明至少具有以下有益效果：
本发明一种性能驱动的多FPGA雅克比模版计算最优部署方法，通过本发明的方法能够在多FPGA协同加速雅克比模版计算中，通过对雅克比六边形分块大小、FPGA芯片进行数学建模，并且通过混合整数线性规划寻优方法，得到最优或者近优的分块方法与放置策略，减少运行耗时，减少能耗。
进一步的，定义雅克比六边形分块的形式化方法，可以进行块间并行运行，并且块内所需数据无需进行片外数据交换，提高了运行效率。
进一步的，设置N种FPGA芯片的属性fn用于后续最优部署策略，对其建模，用于后续的最优化方法中。
进一步的，常量变量的设定，是对六边形分块和FPGA芯片的建模过程，约束是对这些常量与变量的取值、语义等进行约束，目的在于保证部署策略的正确性。
进一步的，定义约束1保证了水平方向的一个六边形分块只能运行于某一个FPGA芯片，不会出现某一分块同属于多个不同FPGA，这是不符合常理的。约束2六边形分块的横向连续性约束，该约束保证了，若某一FPGA运行了多个六边形分块，这些分块是水平连续存在的。约束3保证了任意一个所使用的FPGA芯片型号只能是唯一的，不可能某一FPGA既是n1型号，又是n2型号。约束4约束了开始和结束六边形分块的长度。约束5决定了水平方向六边形分块个数。约束6缓存数据大小与六边形属性关系。约束7-10保证所使用的FPGA芯片资源不能大于FPGA能提供的资源数量。
进一步的，确定目标函数用于最优部署策略，目标函数通过对总成本、资源占用与总耗时三个方面进行多目标优化，在三方面考虑部署效果，相比单一目标而言更全面。
进一步的，通过设施总成本Costsum和所有可选FPGA芯片全部使用时的成本Costmax实现总成本最低，成本最低，使用的FPGA费用最低，比如：如果可以用2块1000元FPGA能够完成运算，就不需要用1块100000元的FPGA。
进一步的，通过所有使用的FPGA芯片占用的各项资源总和Ressum和最大资源数量Resmax确定所占FPGA芯片资源最少，Ressum为完成模版计算所需的FPGA资源，Resmax为FPGA能够提供的最大FPGA，通过使该项目标函数最小化，能够得到最节省资源的运行策略。
进一步的，通过总耗时Latencysum和雅克比模版计算串行执行的耗时Latencymax确定运行总耗时最低，FPGA电路的运行需要耗时，该项目标函数的设置是让耗时最短。
综上所述，本发明考虑了FPGA芯片总成本、资源占用与总耗时三个方面进行多目标优化，各项指标采用线形组合方式，实现模版计算在多FPGA芯片上的最优放置，有效节省FPGA芯片资源浪费，实现模版计算的高效运行，进而节省模版计算的工程开支。
下面通过附图和实施例，对本发明的技术方案做进一步的详细描述。
附图说明
图1为1D Jacobi计算示意图；
图2为1D Jacobi计算示例代码示意图；
图3为1D Jacobi模版六边形分块形式化描述示意图；
图4为1D Jacobi模版六边形分块起始位置定义示意图。
具体实施方式
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
应当理解，当在本说明书和所附权利要求书中使用时，术语“包括”和“包含”指示所描述特征、整体、步骤、操作、元素和/或组件的存在，但并不排除一个或多个其它特征、整体、步骤、操作、元素、组件和/或其集合的存在或添加。
还应当理解，在本发明说明书中所使用的术语仅仅是出于描述特定实施例的目的而并不意在限制本发明。如在本发明说明书和所附权利要求书中所使用的那样，除非上下文清楚地指明其它情况，否则单数形式的“一”、“一个”及“该”意在包括复数形式。
还应当进一步理解，在本发明说明书和所附权利要求书中使用的术语“和/或”是指相关联列出的项中的一个或多个的任何组合以及所有可能组合，并且包括这些组合。
在附图中示出了根据本发明公开实施例的各种结构示意图。这些图并非是按比例绘制的，其中为了清楚表达的目的，放大了某些细节，并且可能省略了某些细节。图中所示出的各种区域、层的形状及它们之间的相对大小、位置关系仅是示例性的，实际中可能由于制造公差或技术限制而有所偏差，并且本领域技术人员根据实际所需可以另外设计具有不同形状、大小、相对位置的区域/层。
本发明提供了一种性能驱动的多FPGA雅克比模版计算最优部署方法，针对雅克比模版计算在高性能计算平台能耗高，运算效率低的问题，本发明提出了多FPGA加速雅克比模版计算方法，首先将模版计算的六边形分块进行形式化描述，其次将FPGA芯片进行数学建模，并且设计了采用MILP(Mixed Integer Linear Programming，混合整数线性规划)的最优化六边形放置策略，通过一系列变量与约束定义，保证了放置的正确运行，最后，本发明考虑FPGA芯片的总成本、资源占用与总耗时三个方面进行多目标优化，各项指标采用线形组合方式，实现了模版计算在多FPGA上的最优放置方法，有效节省了FPGA芯片资源浪费，实现了模版计算的高效运行，进而节省了模版计算的工程开支。
本发明一种性能驱动的多FPGA雅克比模版计算最优部署方法，包括以下步骤：
S1、对雅克比模版计算进行六边形分块，使分块间的数据能够并行运算；
循环分块技术是常见的提高模版计算运行效率的方法，通过将巨大循环迭代空间进行划分，提高模版计算并行度，并且保证分块内数据在得到最大程度重用后才进行访存替换，减少访存操作，提高运行效率。在多FPGA加速中，由于各个FPGA芯片型号不同，所能提供的算力不尽相同，为保证运算的统一性，本发明采用相同大小的雅克比六边形分块策略。
请参阅图3，定义雅克比六边形分块的形式化方法为g＝(ws,wl,h)，其中，g为任意一块六边形计算单元，ws为六边形分块的上下底宽度，wl为中心宽度，h为六边形分块的高，上述三个属性均以cell数量计量，图3中这三项数据分别为：5，9和6。
S2、对运行雅克比模版计算的N种FPGA芯片进行形式化描述，使用数学表示不同FPGA芯片的各项属性；
定义用于模版计算的N种FPGA芯片，对于某一类FPGA芯片fn，将属性定义为其中，fren为芯片频率，/>为芯片各项资源数量，/>为片上带宽，/>为片间带宽，costn为芯片成本。
S3、采用MILP的最优化六边形放置策略对步骤S1的六边形分块和步骤S2的形式化描述内容进行数学建模，确定模型的约束条件，根据FPGA芯片模型的总成本、资源占用与总耗时确定目标函数；
多FPGA的雅克比模版计算放置过程是寻找全局最优解或近优解的过程，本发明定义了采用MILP方法寻求最优的放置策略，将放置问题转化成混合整数线性优化问题，具体寻优过程如下：
S301、常量定义
表1雅克比模版计算放置策略的若干常量定义
S302、变量定义
表2雅克比模版计算放置策略的若干变量定义
S303、约束定义
为了能够保证放置策略的正确运行，将步骤S201的常量与步骤S202的变量进行规约；
六边形分块与所使用的FPGA芯片f所属关系唯一性约束
式(1)保证水平方向的一个六边形分块只能运行于某一个FPGA芯片，具体为：
六边形分块的横向连续性约束
式(2)表示：如果分块kh，kl都运行于FPGA芯片f，且有kh>km>kl，则分块km一定也运行于f，该项约束灵活考虑了异构FPGA芯片所具有的算力不同，可能会导致不同FPGA芯片运行的六边形分块数量不同的情况，通过约束保证运行于同一个FPGA芯片上的多个六边形分块在水平方向上是连续的，具体为：
所使用的FPGA芯片型号唯一性约束
式(3)保证了任意一个所使用的FPGA芯片型号只能是唯一的，具体为：
水平方向上起始与结束六边形分块参数约束
由于采用六边形分块模版计算运行方式的特殊性，定义第一个六边形分块ffirst的位置如图4所示，则根据迭代实例规模的不同，最后一个六边形分块flast的位置不尽相同，式(4)对上述两个分块的宽度进行约束，在规定ffirst分块位置的同时，能够通过约束得到flast分块宽度，具体为：
水平方向六边形分块数量约束
根据式(4)中得到的变量x与wlast，得到分块数量，用式(5)表示，具体为：
缓存数据容量约束
式(6)表示需要与相邻六边形分块进行数据交换的数据容量，如图4所示，与相邻分块的通信数据分别存于bufferleft，buffertop和bufferright中。
资源占用约束
如式(7～10)所示，对于每一块使用的FPGA芯片，其能提供的片上资源数量有限，运算所需的资源不能超过运行芯片的最大可提供资源。
其中，式(7)表示每个使用的芯片f运行的六边形分块个数，具体为：
式(8)通过元素乘运算，计算得到芯片类型n与运行于每个f上的六边形分块个数的关系矩阵，具体为：
cf,n＝b1,f T×pf,n (8)
式(9)通过res()函数点乘运行于每个f上的六边形分块个数，得到每个使用的芯片f所需的各项资源数量，具体为：
式(10)约束所需的各项资源CLB，BRAM，DSP不超过芯片能提供的最大资源数，具体为：
定义目标函数，考虑FPGA芯片的总成本、资源占用与总耗时三个方面进行多目标优化，对各项指标采用线形组合方式，实现模版计算在多FPGA上的最优放置。
从模版计算所用FPGA芯片的总成本、资源占用与总耗时三个方面进行多目标优化，各项指标采用线形组合方式，目标函数如下：
其中，所使用的FPGA芯片的总成本Costsum定义为每种芯片的使用成本costn点乘矩阵p，得到使用的FPGA芯片成本矩阵，求和后得到使用FPGA芯片总成本，如式(12)表示如下：
其中，Costmax为所有可选FPGA芯片全部使用时的成本，用式(13)表示如下：
由水平方向分块的通信耗时latencycomm与运算耗时latencycal之和，乘以迭代次数后得到，总耗时Latencysum用式(14)表示如下：
通信耗时latencycomm用式(15，16)表示，式(15)给出了所使用的FPGA芯片最小片间(inter)、片内(intra)带宽。
如式(16)所示，CLinter表示片间通信延迟最大值，因为片间通信数据为bufferleft和bufferrigth，所以CLinter计算片间最大传输数据量所占时间，相同的，CLintra计算片内最大传输数据量所占时间。因为片内与片间数据传输并行执行，通信总耗时latencycomm为两者最大值。
本发明通过执行周期数与FPGA的执行频率确定运行耗时，多FPGA协作时，运算同步进行，运算耗时由运行最长的FPGA芯片决定，运算耗时latencycal用式(17)表示如下：
Latencymax为h＝1时的总耗时，用式(18)表示如下：
Latencymax＝(latencycomm+latencycal)·T (18)
占用资源(Ressum)为所有使用的FPGA芯片占用的各项资源总和，用式(19)表示如下：
Resmax为所能提供的最大资源数量，用式(20)表示如下：
其中，Costmax，Resmax和Latencymax用于归一化各项代价函数取值，参数w1,w2,w3为各项代价函数权值，满足w1+w2+w3＝1，根据实际需要进行赋值。
S4、通过gurobi最优化工具附带的java函数库对步骤S1得到的雅克比六边形分块的属性、步骤S2得到的FPGA芯片形式化描述内容、步骤S3确定的各项约束条件与目标函数内容进行编写，生成模型文件后通过gurobi工具进行优化得到最优结果，利用最优结果实现最优放置策略。
本发明再一个实施例中，提供一种性能驱动的多FPGA雅克比模版计算最优部署系统，该系统能够用于实现上述性能驱动的多FPGA雅克比模版计算最优部署方法，具体的，该性能驱动的多FPGA雅克比模版计算最优部署系统包括模块、模块、模块以及模块。
其中，分块模块，对雅克比模版计算进行六边形分块，使分块间的数据能够并行运算；
描述模块，对运行雅克比模版计算的N种FPGA芯片进行形式化描述，使用数学表示不同FPGA芯片的各项属性；
函数模块，对分块模块的六边形分块和描述模块的形式化描述内容进行数学建模，确定模型的约束条件，根据FPGA芯片模型的总成本、资源占用与总耗时确定目标函数；
放置模块，对分块模块得到的雅克比六边形分块的属性、描述模块得到的FPGA芯片形式化描述内容、函数模块确定的各项约束条件与目标函数内容进行编写，生成模型文件后优化得到最优结果，利用最优结果实现最优放置策略。
本发明再一个实施例中，提供了一种终端设备，该终端设备包括处理器以及存储器，所述存储器用于存储计算机程序，所述计算机程序包括程序指令，所述处理器用于执行所述计算机存储介质存储的程序指令。处理器可能是中央处理单元(Central ProcessingUnit，CPU)，还可以是其他通用处理器、数字信号处理器(Digital Signal Processor、DSP)、专用集成电路(Application Specific Integrated Circuit，ASIC)、现成可编程门阵列(Field-Programmable GateArray，FPGA)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件等，其是终端的计算核心以及控制核心，其适于实现一条或一条以上指令，具体适于加载并执行一条或一条以上指令从而实现相应方法流程或相应功能；本发明实施例所述的处理器可以用于性能驱动的多FPGA雅克比模版计算最优部署方法的操作，包括：
对雅克比模版计算进行六边形分块，使分块间的数据能够并行运算；对运行雅克比模版计算的N种FPGA芯片进行形式化描述，使用数学表示不同FPGA芯片的各项属性；利用六边形分块和形式化描述内容进行数学建模，确定模型的约束条件，根据FPGA芯片模型的总成本、资源占用与总耗时确定目标函数；对雅克比六边形分块的属性、FPGA芯片形式化描述内容、各项约束条件与目标函数内容进行编写，生成模型文件后优化得到最优结果，利用最优结果实现最优放置策略。
本发明再一个实施例中，本发明还提供了一种存储介质，具体为计算机可读存储介质(Memory)，所述计算机可读存储介质是终端设备中的记忆设备，用于存放程序和数据。可以理解的是，此处的计算机可读存储介质既可以包括终端设备中的内置存储介质，当然也可以包括终端设备所支持的扩展存储介质。计算机可读存储介质提供存储空间，该存储空间存储了终端的操作系统。并且，在该存储空间中还存放了适于被处理器加载并执行的一条或一条以上的指令，这些指令可以是一个或一个以上的计算机程序(包括程序代码)。需要说明的是，此处的计算机可读存储介质可以是高速RAM存储器，也可以是非不稳定的存储器(non-volatile memory)，例如至少一个磁盘存储器。
可由处理器加载并执行计算机可读存储介质中存放的一条或一条以上指令，以实现上述实施例中有关性能驱动的多FPGA雅克比模版计算最优部署方法的相应步骤；计算机可读存储介质中的一条或一条以上指令由处理器加载并执行如下步骤：
对雅克比模版计算进行六边形分块，使分块间的数据能够并行运算；对运行雅克比模版计算的N种FPGA芯片进行形式化描述，使用数学表示不同FPGA芯片的各项属性；利用六边形分块和形式化描述内容进行数学建模，确定模型的约束条件，根据FPGA芯片模型的总成本、资源占用与总耗时确定目标函数；对雅克比六边形分块的属性、FPGA芯片形式化描述内容、各项约束条件与目标函数内容进行编写，生成模型文件后优化得到最优结果，利用最优结果实现最优放置策略。
在T＝4096，h分别取值8～50，ws分别取值28～36，wl取值25的多组实验结果中，本发明的内存数据交换数据次数为2，远低于CPU运行方式下的80～512次，且本发明的能耗为35～42w，远低于CPU运行模式能耗。
综上所述，本发明一种性能驱动的多FPGA雅克比模版计算最优部署方法及系统，针对雅克比模版计算在高性能计算平台能耗高，运算效率低的问题，本发明提出了多FPGA加速雅克比模版计算方法，首先将模版计算的六边形分块进行形式化描述，其次将FPGA芯片进行数学建模，并且设计了采用MILP的最优化六边形放置策略，通过一系列变量与约束定义，保证了放置的正确运行，最后，本发明考虑FPGA芯片的总成本、资源占用与总耗时三个方面进行多目标优化，各项指标采用线形组合方式，实现了模版计算在多FPGA上的最优放置算法，有效节省了FPGA芯片资源浪费，实现了模版计算的高效运行，进而节省了模版计算的工程开支。
本领域内的技术人员应明白，本申请的实施例可提供为方法、系统、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。
本申请是参照根据本申请实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
以上内容仅为说明本发明的技术思想，不能以此限定本发明的保护范围，凡是按照本发明提出的技术思想，在技术方案基础上所做的任何改动，均落入本发明权利要求书的保护范围之内。

Claims (6)

1.一种性能驱动的多FPGA雅克比模版计算最优部署方法，其特征在于，包括以下步骤：
S1、对雅克比模版计算进行六边形分块，使分块间的数据能够并行运算；
S2、对运行雅克比模版计算的N种FPGA芯片进行形式化描述，使用数学表示不同FPGA芯片的各项属性；
S3、对步骤S1的六边形分块和步骤S2的形式化描述内容进行数学建模，确定模型的约束条件，根据FPGA芯片模型的总成本、资源占用与总耗时确定目标函数，目标函数为：
其中，Costsum为FPGA芯片的总成本，Costmax为FPGA芯片全部使用时的成本，Ressum为占用资源，Resmax为最大资源数量，Latencysum为通信总耗时，Latencymax为雅克比模版计算串行执行的耗时，w1,w2,w3为各项代价函数权值；
使用FPGA芯片总成本Costsum如下：
所有可选FPGA芯片全部使用时的成本Costmax表示如下：
其中，F为所使用的FPGA芯片数量，N为FPGA芯片种类，costn为第n种FPGA芯片的成本，f为F中的一个变量，n为N中的一个变量，pf,n为第f个芯片的型号为n；
所有使用的FPGA芯片占用的各项资源总和Ressum表示如下：
最大资源数量Resmax表示如下：
其中，F为所使用的FPGA芯片数量，N为FPGA芯片种类，为，f为F中的任意值，n为N中的任意值，/>为第n种FPGA芯片的各类资源数量；
总耗时Latencysum表示如下：
h＝1时的总耗时的Latencymax表示如下：
Latencymax＝(latencycomm+latencycal)·T
其中，latencycomm为通信耗时，latencycal为运算耗时，T为雅克比模版计算迭代时间步数量，h为六边形分块的高；
S4、利用步骤S1得到的雅克比六边形分块的属性、步骤S2得到的FPGA芯片形式化描述内容、步骤S3确定的各项约束条件与目标函数内容进行编写，生成模型文件后优化得到包括六边形分块的大小，FPGA芯片运行的六边形分块数量和顺序的最优结果，根据最优结果确定最优放置策略。
2.根据权利要求1所述的方法，其特征在于，步骤S1中，定义六边形分块中任意一块六边形计算单元g如下：
g＝(ws,wl,h)
其中，ws为六边形分块的上下底宽度，wl为中心宽度，h为六边形分块的高，ws、wl和h均以cell数量计量。
3.根据权利要求1所述的方法，其特征在于，步骤S2中，N种FPGA芯片的各项属性fn为：
其中，fren为芯片频率，为芯片各项资源数量，/>为片上带宽，/>为片间带宽，costn为芯片成本。
4.根据权利要求1所述的方法，其特征在于，步骤S3中，首先定义雅克比模版计算放置策略的常量，然后定义雅克比模版计算放置策略的变量，对定义的常量和变量进行约束，确定六边形分块与所使用的FPGA芯片f所属关系唯一性约束、六边形分块的横向连续性约束、FPGA芯片型号唯一性约束、水平方向上起始与结束六边形分块参数约束、水平方向六边形分块数量约束、缓存数据容量约束和资源占用约束。
5.根据权利要求4所述的方法，其特征在于，六边形分块与所使用的FPGA芯片所属关系唯一性约束为：
六边形分块的横向连续性约束为：
FPGA芯片型号唯一性约束为：
水平方向上起始与结束六边形分块参数约束为：
wlast＝I-wfirst-x(ws+wl)
水平方向六边形分块数量约束为：
缓存数据容量约束
bufferleft＝h
buffertop＝ws
bufferright＝h
资源占用约束为：
其中，k∈K，F为所使用的FPGA芯片数量，ak,f为第k个六边形分块运行于第f个芯片，kl,km,kh为任意水平方向上的六边形分块，为六边形分块km与所运行的FPGA芯片f的所属关系，/>为六边形分块kl与所运行的FPGA芯片f的所属关系，/>为六边形分块kh与所运行的FPGA芯片f的所属关系，N为FPGA芯片种类，pf,n为第f个芯片的型号为n，wfirst为水平方向上第一个六边形分块的宽度，h为六边形分块的高，ws为六边形分块的上下底宽度，wl为六边形分块的中心宽度，wlast为水平方向上最后一个六边形分块的宽度，x为正整数，K为水平方向的六边形分块数量，bufferleft为六边形分块左侧需保存在缓存中的数据量，buffertop为六边形分块顶部需保存在缓存中的数据量，bufferright为六边形分块右侧需保存在缓存中的数据量，R为FPGA芯片资源种类，/>为运行在第f块FPGA所需的第r种资源数量，/>为第n种FPGA芯片的各类资源数量。
6.一种性能驱动的多FPGA雅克比模版计算最优部署系统，其特征在于，包括：
分块模块，对雅克比模版计算进行六边形分块，使分块间的数据能够并行运算；
描述模块，对运行雅克比模版计算的N种FPGA芯片进行形式化描述，使用数学表示不同FPGA芯片的各项属性；
函数模块，对分块模块的六边形分块和描述模块的形式化描述内容进行数学建模，确定模型的约束条件，根据FPGA芯片模型的总成本、资源占用与总耗时确定目标函数；
目标函数为：
其中，Costsum为FPGA芯片的总成本，Costmax为FPGA芯片全部使用时的成本，Ressum为占用资源，Resmax为最大资源数量，Latencysum为通信总耗时，Latencymax为雅克比模版计算串行执行的耗时，w1,w2,w3为各项代价函数权值；
使用FPGA芯片总成本Costsum如下：
所有可选FPGA芯片全部使用时的成本Costmax表示如下：
其中，F为所使用的FPGA芯片数量，N为FPGA芯片种类，costn为第n种FPGA芯片的成本，f为F中的一个变量，n为N中的一个变量，pf,n为第f个芯片的型号为n；
所有使用的FPGA芯片占用的各项资源总和Ressum表示如下：
最大资源数量Resmax表示如下：
其中，F为所使用的FPGA芯片数量，N为FPGA芯片种类，为，f为F中的任意值，n为N中的任意值，/>为第n种FPGA芯片的各类资源数量；
总耗时Latencysum表示如下：
h＝1时的总耗时的Latencymax表示如下：
Latencymax＝(latencycomm+latencycal)·T
其中，latencycomm为通信耗时，latencycal为运算耗时，T为雅克比模版计算迭代时间步数量，h为六边形分块的高；
放置模块，对分块模块得到的雅克比六边形分块的属性、描述模块得到的FPGA芯片形式化描述内容、函数模块确定的各项约束条件与目标函数内容进行编写，生成模型文件后优化得到包括六边形分块的大小，FPGA芯片运行的六边形分块数量和顺序的最优结果，根据最优结果确定最优放置策略。
CN202110528857.0A 2021-05-14 2021-05-14 一种性能驱动的多fpga雅克比模版计算最优部署方法及系统 Active CN113255269B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202110528857.0A CN113255269B (zh) 2021-05-14 2021-05-14 一种性能驱动的多fpga雅克比模版计算最优部署方法及系统

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202110528857.0A CN113255269B (zh) 2021-05-14 2021-05-14 一种性能驱动的多fpga雅克比模版计算最优部署方法及系统

Publications (2)

Publication Number Publication Date
CN113255269A CN113255269A (zh) 2021-08-13
CN113255269B true CN113255269B (zh) 2024-04-02

Family

ID=77181978

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202110528857.0A Active CN113255269B (zh) 2021-05-14 2021-05-14 一种性能驱动的多fpga雅克比模版计算最优部署方法及系统

Country Status (1)

Country Link
CN (1) CN113255269B (zh)

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9606964B1 (en) * 2015-12-30 2017-03-28 International Business Machines Corporation Visual modeller for mathematical optimization
CN111381886A (zh) * 2020-03-02 2020-07-07 西安交通大学 一种针对模板计算的菱形分块并行优化方法
CN112632465A (zh) * 2021-03-05 2021-04-09 之江实验室 基于fpga的实对称矩阵特征值分解的数据存储方法

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10878038B2 (en) * 2018-12-14 2020-12-29 The Boeing Company Searching multimodal spaces

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9606964B1 (en) * 2015-12-30 2017-03-28 International Business Machines Corporation Visual modeller for mathematical optimization
CN111381886A (zh) * 2020-03-02 2020-07-07 西安交通大学 一种针对模板计算的菱形分块并行优化方法
CN112632465A (zh) * 2021-03-05 2021-04-09 之江实验室 基于fpga的实对称矩阵特征值分解的数据存储方法

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
林一松 ; 杨学军 ; 唐滔 ; 王桂彬 ; 徐新海 ; .一种基于并行度分析模型的GPU功耗优化技术.计算机学报.2011,(04),全文. *

Also Published As

Publication number Publication date
CN113255269A (zh) 2021-08-13

Similar Documents

Publication Publication Date Title
Zachariadis et al. Accelerating sparse matrix–matrix multiplication with GPU Tensor Cores
Zeng et al. GraphACT: Accelerating GCN training on CPU-FPGA heterogeneous platforms
CN111459877B (zh) 基于FPGA加速的Winograd YOLOv2目标检测模型方法
Papa et al. Hypergraph Partitioning and Clustering.
US20250005455A1 (en) Partitioning for an execution pipeline
CN105808339A (zh) 大数据并行计算方法及装置
US20200090051A1 (en) Optimization problem operation method and apparatus
Dhar et al. GDP: GPU accelerated detailed placement
Montone et al. Placement and floorplanning in dynamically reconfigurable FPGAs
Bernaschi et al. A factored sparse approximate inverse preconditioned conjugate gradient solver on graphics processing units
Marconi Online scheduling and placement of hardware tasks with multiple variants on dynamically reconfigurable field-programmable gate arrays
Wu Review on FPGA-based accelerators in deep learning
Du et al. Improving computation and memory efficiency for real-world transformer inference on gpus
CN113255269B (zh) 一种性能驱动的多fpga雅克比模版计算最优部署方法及系统
Salinas-Hilburg et al. Energy-aware task scheduling in data centers using an application signature
Moreno et al. Improving the performance and energy of non-dominated sorting for evolutionary multiobjective optimization on GPU/CPU platforms
Cecconi et al. Optimal tiling strategy for memory bandwidth reduction for cnns
Lee et al. HyperG: Multilevel GPU-Accelerated k-way Hypergraph Partitioner
Kiran et al. Development of GPU‐based matrix‐free strategies for large‐scale elastoplasticity analysis using conjugate gradient solver
Jung et al. Accelerating implicit integration in multi-body dynamics using GPU computing
Cambier et al. A task-based distributed parallel sparsified nested dissection algorithm
CN113255270B (zh) 一种雅克比模版计算加速方法、系统、介质及存储设备
Mahapatra et al. DFG partitioning algorithms for coarse grained reconfigurable array assisted RTL simulation accelerators
US20230325464A1 (en) Hpc framework for accelerating sparse cholesky factorization on fpgas
Mohtavipour et al. A quad-form clustered mapping approach for large-scale applications of reconfigurable computing systems

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant