2.2 基于任务就绪列表的基本映射策略
基于任务就绪列表的无死锁基本映射策略根据输入的密码处理任务Gf和RCCPA的结构模型，在满足约束条件的前提下，通过建立任务就绪列表避免死锁，输出为能够处理一个分组的基本配置序列.主要分为以下步骤：
Step1 建立未分配任务集合、已分配任务集合，初始情况下未分配任务集合Gn=Gf，已分配任务集合Gp=.
Step2 根据未分配任务集合Gn和已分配任务集合Gp，生成就绪任务列表Gr，其过程是对Gn中的每个节点v，考查该节点的所有前驱节点prev（v）是否已经被分配到相应的模块，即判断prev（v）是否属于Gp，如果所有的前驱节点属于Gp，则该节点为就绪节点.就绪列表建立算法如下描述.
输入：未分配任务集合Gn和已分配任务集合Gp
输出：就绪任务节点集合Gr
Gr=；初始化就绪节点集合为空集
For each node v∈Gndo；遍历未分配任务集合Gn中的所有节点
sign←0； //初始化标记
For each node u∈prev（v） do；
If uGp； //尚未分配节点
sign←1；//标记为非就绪节点
Break；
Endif
Endfor
If sign=0then //v为就绪节点
Gr=Gr∪v； //将v加入到节点就绪集合中
Endif
endforStep3 根据就绪任务集合Gr，RCCPA的资源约束情况，确定第i次（第1次执行此步骤时i=1）任务分配生成的配置序列2i-1，2i.为就绪集合中的任务分配单元时，需要按照一定的规则进行.本文设置的分配规则为：1）尽量将存在通信关系的任务分配到相同的处理簇中；2）任务分配按照优先分配处理簇1， 然后分配处理簇2，3，4中单元的顺序进行.为硬件任务分配资源时，尽量满足规则1），在不能满足规则1）的情况下按照规则2）进行分配.分配算法的伪码描述如下.
输入：就绪任务集合Gr，RCCPA的资源约束Rtotal[y][x]，MRtotal，未分配任务集合Gn和已分配任务集合Gp
输出：配置序列2i-1，2i，更新后的未分配任务集合Gn和已分配任务集合Gp
2i-1=，2i=；初始化配置序列为空集
n=card（Gr）；提取就绪列表中的任务个数
For j=0， j++， j
（sign，2i-1，2i）←map（v，2i-1，2i）；
//根据分配原则、资源约束，2i-1，2i的资源使用情况为任务v分配资源，生成新的配置序列.若v分配成功，则置sign=0，更新2i-1，2i，否则sign=1，2i-1，2i序列不变.
If sign=0 then
{Gr，Gn，Gp}←updata{v，Gr，Gn，Gp}；
//分配成功，更新各任务集合
Else Gr=Gr-v；分配失败，更新就绪任务集合
Endif
Endfor
Step4 判断未分配任务集合是否为空集.若Gn≠表示尚有任务未分配，则返回Step2继续执行.若Gn=则表明任务分配完毕，将Step3生成的配置序列={1，2，…，s}依次输出，即为生成的初始配置上下文序列.
基本映射策略采用建立任务就绪列表的方式进行任务分配，保证了每次分配的任务均是就绪节点，杜绝了任务分配时死锁的出现.按照约定的分配原则进行任务分配，保证了每次循环至少可以完成一个任务节点的分配，并保证了不会出现资源冲突，经多次循环后可以完成所有任务的分配.
设输入任务图的节点数目和边数分别为|V|和|E|，对于基本映射策略的主循环，每次搜索就绪任务列表，至少可以分配一个子任务，因此最坏情况下只需要搜索|V|次就绪列表就可以完成任务分配.对于每次循环都需要计算一次就绪任务列表，建立就绪列表需要搜索任务中的所有节点和每个节点的所有前驱，因此复杂度为O（|V|+|E|）.另外，每次循环都需要搜索就绪列表，其时间复杂度为|L|，其中|L|为就绪列表中包含的任务个数，|L|≤|V|.因此基本映射策略的时间复杂度上界为（|V|）（|V|+|E|+|V|），即基本策略的复杂度为O（|V|2+|V||E|）.
2.3 基于并行优化的映射策略
RCCPA基本架构提供了4个32 bit的处理簇，通过基本映射策略进行任务分配时，会出现4个处理簇没有完全占用的情况；为开发分组密码组内的并行性，充分利用各处理簇硬件资源，在基本映射策略的基础上，提出了基于并行优化的映射策略.该策略是为了利用基本配置策略没有占用的处理簇资源，因此并行优化映射序列时，不需要考虑系统的资源约束和存储约束.并行优化策略描述如下.
Step1 搜索初始配置序列={1，2，…，s}中占用的功能单元所对应的处理簇的最大编号max，max即为初始配置序列共占用的处理簇个数，其伪码描述如下：
max =1； //初始化最大编号
for each i∈ do //遍历所有的配置序列
for each ri[y][x]∈i do
if y
else max =y； //更新max
endif
endfor
RCBCP是一款采用VLIW结构具有4路并行的可重构分簇式密码处理器，Crypto-nite为两路并行的64 bit位宽RISC结构，RCPA是基于阵列结构的可重构密码处理架构.通过对多种分组密码算法的适配，从表2的对比结果可以得出，RCCPA结构可以灵活适配分组密码算法，并且对不同设计结构、不同处理位宽、不同操作位宽的分组密码算法均有较高的处理性能，与其他专用可重构密码处理结构相比处理性能提高了1.3～5.8倍.
