基于倒计时缓冲的GPDSP汇编移植优化方法及系统

摘要

本发明公开了一种基于倒计时缓冲的GPDSP汇编移植优化方法及系统，本发明针对汇编代码进行解析并基于倒计时缓冲池进行依赖分析构建指令依赖的有向无环图；分析移植前后指令集信息的差异，根据移植前后指令集信息的差异对汇编代码中指令进行修正，将其移植映射到新体系结构下的指令信息；基于指令依赖的有向无环图、移植映射到新体系结构下的指令信息基于长指令优先的列表调度算法进行指令的并行优化打包调度，得到移植到新体系结构下的目标汇编代码。本发明能够使汇编代码在不同代GPDSP平台上实现有效的自动迁移，能够将原有的汇编代码进行重新的并行打包调度，并取得更好的代码性能和硬件资源利用率。

说明书

技术领域

本发明涉及汇编代码优化与移植领域，具体涉及一种基于倒计时缓冲的GPDSP汇编移植优化方法及系统。

背景技术

GPDSP(General Purpose DSP，通用数字信号处理器)近年来得到了长足的发展与进步，并广泛应用于无线通信、科学计算、图像处理等多个领域，同时也逐渐渗透到人们的日常生活中，逐步成为消费级电子产品的核心。目前GPDSP大多具有向量处理、单指令多数据(Single Instruction Multiple Data，SIMD)支持和超长指令字(Very LongInstruction Word，VLIW)的特征，支持浮点和定点计算，我国自主研发的FT-Matrix系列和德州仪器公司的DSP就是其中的典型代表。

GPDSP当前支持的主流编程方式除了通用C语言外，为了进一步提升其体系结构，尤其是向量单元的利用效率，通常采用基于C的向量扩展+汇编语言的混合编程模式提供给用户进行编程开发。对于一般用户而言向量C的编程可以满足需求，但是对于底层算法库的开发人员或对核心算算法性能有严格要求的程序员则需要采用汇编语言来最大化核心代码的性能优化和资源利用效率，因此汇编语言编程对于GPDSP的性能具有至关重要的作用。

汇编语言进行编程开发，需要程序员直接看到底层体系结构的信息，同时根据指令集手动静态排布所有的指令流。虽然能够完成高效的算法设计实现，但是其所需的技术积累、人力成本和开发周期都是极高的，且代码不具有良好的可移植性。具体来说：第一，对于用户的核心级汇编代码，需要手动对指令进行并行排布，同时需要考虑指令间的依赖关系、指令节拍数、延迟槽隐藏、功能单元限制和指令并行打包等等，尤其在核心级代码较长的时候，人力有时无法在众多约束下找到一个较优的并行排布方案，因此汇编代码的开发和优化具有极大的难度；第二，由于汇编代码通常是静态排布的，往往已经包含了部分延迟槽隐藏的优化，因此如果对汇编代码进行优化，首先需要对原有汇编代码中的指令进行解析与依赖分析。而这其中最复杂的在于需要根据汇编指令的节拍数，屏蔽掉延迟槽隐藏，并分析出其中原有的指令流顺序和指令间依赖关系，这个是极为困难的；第三，在产品迭代的过程中，如果新一代DSP产品体系结构上功能单元配置、寄存器文件配置或指令集文件出现部分修改，则上一代的汇编代码不具有继承性，因此需要重新进行开发，浪费人力财力。

发明内容

本发明要解决的技术问题为：针对现有技术的上述问题，为了实现对GPDSP上汇编代码进行性能优化，并提高在不同代产品上的代码可移植性，提供一种基于倒计时缓冲的GPDSP汇编移植优化方法及系统，以实现GPDSP汇编程序跨平台、版本的移植与性能优化，本发明能够使汇编代码在不同代GPDSP平台上实现有效的自动迁移，能够将原有的汇编代码进行重新的并行打包调度，并取得更好的代码性能和硬件资源利用率。

为了解决上述技术问题，本发明采用的技术方案为：

一种基于倒计时缓冲的GPDSP汇编移植优化方法，包括：

1)针对待移植的GPDSP汇编代码进行解析，并基于倒计时缓冲池进行依赖分析，分析出其中的指令流顺序和指令间的依赖关系并构建指令依赖的有向无环图；

2)分析移植前后指令集信息的差异，根据移植前后指令集信息的差异对汇编代码中指令进行修正，将其移植映射到新体系结构下的指令信息；

3)基于指令依赖的有向无环图、移植映射到新体系结构下的指令信息基于长指令优先的列表调度算法进行指令的并行优化打包调度，得到移植到新体系结构下的目标汇编代码。

可选地，步骤1)中基于倒计时缓冲池进行依赖分析的步骤包括：构建缓冲池和已生效指令池，并在缓冲池的外部维护一个用于倒计时的时钟，将汇编代码中的指令按显式顺序压入缓冲池，并按照指令的生效时间依次将指令弹出缓冲池，且在弹出缓冲池时首先在已生效指令池中寻找已生效的指令并建立依赖关系、然后再加入已生效指令池，从而得到分析出其中的指令流顺序和指令间的依赖关系。

可选地，步骤1)中指令间的依赖关系表示为三元组表示(Instr_x,Instr_y,num)，其中Instr_x代表父指令，Instr_y代表子指令，num代表父指令和子指令之间需要空的节拍数。

可选地，父指令和子指令之间需要空的节拍数num为正值或负值，其中负值表示子指令提前执行但在父指令生效之后才生效。

可选地，步骤2)中移植前后指令集信息的差异包括指令名称的改变或调整、指令节拍数变化以及可执行功能单元的变化。

可选地，步骤2)中对汇编代码中指令进行修正包括：针对指令名称的改变或调整，对汇编代码中指令一一对应进行自动替换；针对指令节拍数变化，对汇编代码中指令的指令节拍进行修正，同时调整与该指令有依赖关系；针对可执行功能单元的变化，对汇编代码中指令的可执行功能单元一一对应进行修正。

可选地，步骤3)包括：

3.1)创建一个调度表，所述调度表用于记录每一个时钟周期内每一个功能单元是否被占用，每一条指令除了维护一个可执行功能单元列表外，还需要维护一个可以最早开始执行的时钟周期；对有向无环图中的指令进行拓扑排序，无被指向依赖关系的父指令将会被加入调度队列中，其最早可以开始执行的始终钟周期为1；

3.2)从有向无环图中弹出一个指令作为调度对象；

3.3)根据作为调度对象的指令的可执行功能单元列表，对应查看调度表，选择放在可以最早执行的且空闲的功能单元上，同时标注开始执行的时钟周期，更新调度表占用情况；将该指令指向其他子指令的依赖关系全部删除，并根据该指令开始的时钟周期和依赖关系中的依赖周期之和修改子指令的最早可以开始的时钟周期；

3.4)判断有向无环图是否已经遍历完毕，若尚未遍历完毕，则跳转执行步骤3.2)；否则，根据调度表生成新体系结构下的目标汇编代码。

可选地，步骤3.2)中从有向无环图中弹出一个指令作为调度对象时，如果同时存在多个符合条件的指令，优先弹出指令周期长的指令作为调度对象。

此外，本发明还提供一种基于倒计时缓冲的GPDSP汇编移植优化系统，包括相互连接的微处理器和存储器，所述微处理器被编程或配置以执行所述基于倒计时缓冲的GPDSP汇编移植优化方法的步骤。

此外，本发明还提供一种计算机可读存储介质，该计算机可读存储介质中存储有被编程或配置以执行所述基于倒计时缓冲的GPDSP汇编移植优化方法的计算机程序。

和现有技术相比，本发明主要具有下述优点：

1、本发明提出的汇编代码依赖分析方法适用于GPDSP平台，可通过指令集信息完成对静态排布好的汇编代码进行指令时序逻辑的解析和指令间的依赖分析。

2、本发明提出的面向新体系结构的汇编代码移植方法，可以使汇编代码在不同代GPDSP平台上实现有效的自动迁移。

3、本发明提出的GPDPS汇编代码优化方法，基于长指令优先的列表调度算法能够将原有的汇编代码进行重新的并行打包调度，并取得更好的代码性能和硬件资源利用率。

附图说明

图1为本发明实施例方法的整体结构图。

图2为本发明实施例方法中基于倒计时缓冲的依赖分析流程图。

图3为本发明实施例方法中的指令调度流程图。

具体实施方式

如图1所示，本实施例基于倒计时缓冲的GPDSP汇编移植优化方法包括：

1)针对待移植的GPDSP汇编代码(图1中以后缀名“.asm”表示)进行解析，并基于倒计时缓冲池进行依赖分析，分析出其中的指令流顺序和指令间的依赖关系并构建指令依赖的有向无环图；

2)分析移植前后指令集信息的差异，根据移植前后指令集信息的差异对汇编代码中指令进行修正，将其移植映射到新体系结构下的指令信息；

3)基于指令依赖的有向无环图、移植映射到新体系结构下的指令信息基于长指令优先的列表调度算法进行指令的并行优化打包调度，得到移植到新体系结构下的目标汇编代码(图1中仍以后缀名“.asm”表示)。

用户的汇编代码中每一行通常为一条汇编指令，由于GPDSP汇编代码通常是经过静态排布的，仅仅从代码上显式的只能看出每条指令是在哪一拍开始执行，经过该指令的延迟槽节拍数后，才能执行完成并生效，这一点很难直接通过代码看出来，尤其是经过优化延迟槽后的汇编代码,其中已经包括了指令排布和延迟槽隐藏。因此要对汇编代码进行优化，首先需要对该代码进行解析，分析出其中的指令流顺序和指令间的依赖关系，才可以对代码进行优化和移植。

从汇编代码上可以显式看出每条指令启动的时钟周期，同时结合指令集中每条指令的执行节拍，可以推断出在哪一拍该指令可以生效。根据上述原则，本实施例提出一种基于倒计时缓冲的机制，来梳理所有汇编指令流生效及依赖关系。具体地，如图2所示，本实施例步骤1)中基于倒计时缓冲池进行依赖分析的步骤包括：构建缓冲池和已生效指令池，并在缓冲池的外部维护一个用于倒计时的时钟，将汇编代码中的指令按显式顺序压入缓冲池，并按照指令的生效时间依次将指令弹出缓冲池，且在弹出缓冲池时首先在已生效指令池中寻找已生效的指令并建立依赖关系、然后再加入已生效指令池，从而得到分析出其中的指令流顺序和指令间的依赖关系。本实施例中通过上述倒计时缓冲的设置可以完成对整个指令流与依赖关系的分析，构建出指令依赖的有向无环图。

参见图2，执行依赖分析前需要外部提供指令集信息，即每种指令具体的名称、可执行功能单元和具体的节拍数。依赖分析模块外部将维护一个时钟，用来记录当前的时钟周期，然后按照代码的顺序依次读取当前节拍要执行的汇编指令并解析，将指令放入一个缓冲池。压入缓冲池的指令将根据开始执行的时钟周期与指令集中提供的该指令执行节拍数相加，计算得出预计完成的时间，并在该指令中保存该记录。同时依赖分析模块在每一拍都需要遍历当前倒计时缓冲中的所有指令，判断是否有指令已经在当前时钟执行完成，生效的指令将依次从该缓冲池中弹出，并进行后续的依赖分析和调度。

生效弹出的指令可以根据具体的操作进行数据依赖(包括读后写、写后写、写后读)和控制依赖的分析。本实施例中，步骤1)中指令间的依赖关系表示为三元组表示(Instr_x,Instr_y,num)，其中Instr_x代表父指令，Instr_y代表子指令，num代表父指令和子指令之间需要空的节拍数。以写后读为例，如果Instr_x指令写入的操作数与Instr_y指令读取的操作数有数据依赖，而Instr_x的执行节拍为cycle_x，那么两条指令之间的依赖关系可以描述为(Instr_x,Instr_y,cycle_x)。

其中，父指令和子指令之间需要空的节拍数num为正值或负值，其中负值表示子指令提前执行但在父指令生效之后才生效。由于操作数的读取生效通常是在执行节拍的第一拍，而操作数写入生效通常是在执行节拍的最后一拍，因此在遇到写后写或读后写依赖时，num的值是可以为负值的，即可以写指令提前执行但在读指令生效之后才生效。通过上述倒计时缓冲机制，我们可以分析出源代码中指令流的时序逻辑，并按照生效时间依次为指令进行依赖分析，构建出指令依赖的有向无环图，从而为后续指令调度优化奠定基础。

同系列的GPDSP产品通常来说体系结构并不会有太大的改变，但是对于汇编编程而言，即使改变不大还是可能导致程序无法直接移植，而且由于应用场景或工艺等方面的改进和调整往往会使得与指令集相关的部分信息会发生变化，而这些与体系结构紧耦合的变化会导致汇编代码无法移植直接使用。为了完成不同代产品之间代码的迁移，需要分析两者之间指令集信息的差异，并通过对汇编代码的分析，完成新体系结构下指令信息的映射。

本实施例中，步骤2)中移植前后指令集信息的差异包括指令名称的改变或调整、指令节拍数变化以及可执行功能单元的变化。

本实施例中，步骤2)中对汇编代码中指令进行修正包括：针对指令名称的改变或调整，对汇编代码中指令一一对应进行自动替换；针对指令节拍数变化，对汇编代码中指令的指令节拍进行修正，同时调整与该指令有依赖关系；针对可执行功能单元的变化，对汇编代码中指令的可执行功能单元一一对应进行修正。在指令集信息差异表的辅助下，本发明可以对汇编代码解析和依赖分析的基础上，针对新体系结构进行映射，具体映射包括以下几个方面：1)将源代码中所有的汇编指令进行遍历，遇到指令名称有变化的，可以将其对应替换为新的名称；2)修改体系结构中有关功能单元描述的数据结构，将功能单元的种类和数目以新体系结构为准，后续将参照新的功能单元进行指令调度；3)参照新的指令集信息，对每个指令维护的可执行功能单元列表以及节拍数进行更新；4)对于有依赖关系的指令Instr_x，其执行节拍数cycle_x如果有调整，需要对应重新计算其相关的每一个依赖关系三元组(Instr_x，Instr_y，num)。在上述几个方面的分析映射基础上，可以将原有的汇编代码完成面向新体系结构的指令映射，同时对依赖关系也进行相应的调整，以便于后续指令调度和代码生成。通过上述针对性的调整映射，可以完成源代码在新体系结构下的映射移植，可以直接完成不同代DSP产品之间汇编代码的自动迁移，大大提高软件生态的可移植性，提高软件开发效率。

在完成指令依赖分析和新体系结构映射的基础上，通过指令的并行打包调度，可以生成高效的汇编代码，从而提高整个程序的执行效率。在依赖分析生成的指令有向无环图上，将指令进行拓扑排序，然后按照排序后的指令将根节点首先加入调度队列。调度队列每次将弹出一个指令执行调度过程。为了完成指令调度，我们将维护一个指令排布表，横轴为硬件所有的功能单元，纵轴为时间周期，每个指令除了保留之前的依赖关系和可执行的功能单元列表外，还将维护一个最晚开始执行时间的时间戳。首次加入调度队列的根节点，其最晚开始执行时间均为0。从调度队列中弹出执行调度过程的指令，将根据自身功能单元约束及最晚开始时间约束，按照行优先在指令排布表中找可以放置的位置，遇到最早可以执行的功能单元之后，将在指令排布表中预约该功能单元，预约的时间为从该指令开始执行的时钟周期到其指令执行完毕。以Instr_x为例，假设其最晚开始执行时间为第i拍，通过行优先查找，发现在第i+j拍可以选择功能单元n占用执行，因此将在指令排布表上预约功能单元n的第i+j拍到第i+j+cycle_x拍。完成当前指令的调度后，需要将该指令指向其他指令的依赖关系删除，同时对其子指令的最晚执行时间修改为当前指令的执行节拍+两指令之间的依赖节拍之和。还是以上面Instr_x指令为例，假设该指令已确定第i+j拍开始执行，而Instr_y和Instr_x存在依赖关系(Instr_x，Instr_y，num)，且Instr_y的原最晚开始时间为time_y，则Instr_y的最晚开始时间将修改为max(time_y，i+j+num)。而每次调度完一条指令，可以将新产生的根节点指令重新加入调度队列。调度队列采用的是优先队列来实现，当同时存在多个根节点时，执行节拍数较长的将优先进行调度。重复该调度过程，直到所有指令均已调度完毕，根据最后生成的指令排布表生成最终优化后的新汇编代码。

作为一种优选的实施方式，如图3所示，本实施例步骤3)包括：

3.1)创建一个调度表，调度表用于记录每一个时钟周期内每一个功能单元是否被占用(记录资源约束)，每一条指令除了维护一个可执行功能单元列表外，还需要维护一个可以最早开始执行的时钟周期；对有向无环图中的指令进行拓扑排序，无被指向依赖关系的父指令将会被加入调度队列中，其最早可以开始执行的始终钟周期为1；

3.2)从有向无环图中弹出一个指令作为调度对象；

3.3)根据作为调度对象的指令的可执行功能单元列表，对应查看调度表，选择放在可以最早执行的且空闲的功能单元上，同时标注开始执行的时钟周期，更新调度表占用情况；将该指令指向其他子指令的依赖关系全部删除，并根据该指令开始的时钟周期和依赖关系中的依赖周期之和修改子指令的最早可以开始的时钟周期；

3.4)判断有向无环图是否已经遍历完毕，若尚未遍历完毕，则跳转执行步骤3.2)；否则，根据调度表生成新体系结构下的目标汇编代码。

本实施例步骤3)基于长指令优先的列表调度算法进行指令的并行优化打包调度具体为采用面向VLIW的长指令优先的列表调度改进算法。步骤3.2)中从有向无环图中弹出一个指令作为调度对象时，如果同时存在多个符合条件的指令，优先弹出指令周期长的指令作为调度对象。

综上所述，面向GPDSP开发的汇编代码，由于经过编译器或人工排布，可能已经存在了延迟槽隐藏和并行打包优化。如果需要对该汇编代码进行优化或移植，需要首先分析该代码中的指令生效节拍和指令间依赖关系。然后在依赖分析的基础上对代码进行新的并行排布优化或移植。针对上述问题，本实施例方法针对汇编代码进行解析，并基于倒计时缓冲池进行依赖分析，分析出其中的指令流顺序和指令间的依赖关系并构建指令依赖的有向无环图；分析移植前后指令集信息的差异，根据移植前后指令集信息的差异对汇编代码中指令进行修正，将其移植映射到新体系结构下的指令信息；基于指令依赖的有向无环图、移植映射到新体系结构下的指令信息基于长指令优先的列表调度算法进行指令的并行优化打包调度，得到移植到新体系结构下的目标汇编代码。基于倒计时缓冲机制完成指令依赖的分析和有向无环图的构建，同时可以完成新体系结构的指令集信息映射，并对指令进行高效调度，提高算法性能和可移植性。本实施例方法能够使汇编代码在不同代GPDSP平台上实现有效的自动迁移，能够将原有的汇编代码进行重新的并行打包调度，并取得更好的代码性能和硬件资源利用率。

此外，本实施例还提供一种基于倒计时缓冲的GPDSP汇编移植优化系统，包括相互连接的微处理器和存储器，所述微处理器被编程或配置以执行前述基于倒计时缓冲的GPDSP汇编移植优化方法的步骤。

此外，本实施例还提供一种计算机可读存储介质，该计算机可读存储介质中存储有被编程或配置以执行前述基于倒计时缓冲的GPDSP汇编移植优化方法的计算机程序。

显然，本领域的技术人员可以根据本发明的技术构思对本发明进行各种改动和变形，而这些修改和变形属于本发明权利要求及等同技术范围之内，则都应属于本发明权利要求的保护范围。