摘 要 针对 可重构设计中高效率的资源分配面临的困难，提出基于共享度的 可重构设计算法 描述基于共享度对 资源分配策略的实施过程，并给出基于共享度的资源分配最优策略及证明过程 经过模拟测试表明，所设计的 资源分配算法在资源利用率和任务平均等待延时方面均优于传统的 算法，其平均任务等待延时比传统的 算法缩短了
关键词 可重构 资源分配 共享度 算法
　　引 言
　　利用 进行可重构设计可以充分发挥 资源的灵活性，同时也能够提高 资源的利用率，是目前一种有效的以较小的代价实现较复杂的逻辑功能的途径［ ］然而，在可重构设计过程中，面临的一个最大的难点是如何设计优秀的资源布局算法，对可重构任务进行合理的资源分配，以提高的资源利用率，然而由于 内部结构差异比较大，既有比较通用的 资源模块，也有具备专用功能的存储模块，因此不能够采用一种统一的模式对 的资源进行分配和管理［，］另一方面，进行可重构设计的任务产生本身具有突发性，难以对即将要产生的应用任务其需求的 资源进行预测和预估，从而增加了 算法的设计难度［，］，因此，如何设计一个合理的可重构设计资源分配算法，是目前面临的一个难点
　　目前，针对 可重构设计资源分配算法开展的研究主要有中国科学技术大学的任永青在其博士论文中，研究了逻辑核动态可重构的众核处理器体系结构设计与实现的相关问题［］中国科学院研究生院的周盛雨对基于 的动态部分重构系统的实现开展了深入研究［］研究了可重构系统的设计原理和实现关键技术，尤其是对可重构设计中的资源分配开展了深入研究 南开大学的李涛杨愚鲁等重点对可重构设计中的硬件任务布局的算法开展了深入研究［］，提出了基于任务上边界计算最大空闲矩形的算法，该算法是在传统的 算法和 算法基础上进行改进，并且获得了较好的资源利用率目前这些算法在研究 资源动态分配时，都是采用基于启发式的策略，但并没有对等待分配资源任务的前后关系进行研究，也并没有从局部整 体 上 分 析 资源动态分配策略［，］本文结合 中的资源结构特点，采用任务窗口的形式缓解待分配资源任务到来的突发性，以期更好的资源分配效果
　　共享度的提出
　　共享度的定义共享度: 共享度指 中的基本逻辑资源单元可被多个任务共享占用的程度，以可被共享占用任务的数目进行描述
　　本文所定义的共享度是用于描述 中的逻辑资源可以被分配给不同任务的程度，为了能够定量地分析，要求 中的逻辑资源能够被划分为大小一定的基本逻辑单元，而且能够对各个任务准确地描述其占用逻辑单元的范围，以此实现各个逻辑单元的共享度计数利用共享度对 中可用资源的描述假设 中所有可用资源范围在二维坐标系下可描述为( ) ( ) ， 等待分配至 中的任务集合记为 { ，，，} ，总 任 务 数 为 ，任 意 一 个 任 务( ) 可被分配至 中的坐标集合为 :{ ( ，) ， } ( )其中 ， ， 和 分别代表任务需要的资源空间二维坐标系下的尺寸表示 集合中的元素个数一个基本逻辑资源单元( ，) 对任务 可被分配的度记为( ，，) ， 其计算式为:( ，，) { ( ，) ? : } ( )对于 中，任意一个可用基本逻辑单元( ，) 的共享度为 ( ，) :( ，) ( ，，) ( )对于 公司 系列 中的可用资源分为和 两种类 型，而 且 的资源数远少于类型的资源数，为了能够区分计算这两类资源数在计算共享度时的差别，将式( ) 修改为:( ，) ( ，， )( ，， ) ( )针对等待分配资源的任务集合 中的所有任务，并不是都同时到达集合中，因此每个任务等待资源分配的时间也不尽相同，一个公平的资源分配算法除了需要考虑尽可能提高资源利用率，同时还需要增加对任务等待时间的考虑 因此，本文在建立资源共享度描述方式时，引入了各个任务进入窗口后的等待时间 ，而且 和 两种类型可以使用不同的影响因子，因此得到如式( ) 所示的共享度计算方法( ，) ( ) ( ，， )( ) ( ，， ) ( )基于共享度的资源分配算法设计最佳分配策略根据本文定义的共享度的概念，提出了一种基于共享度的资源分配策略: 共享度越低的资源空间表明其可被其他任务使用的可能性越小，该资源空间则应优先被分配掉 共享度越高的资源空间表明其通用程度越过，则此类空间应该更靠后分配定理 优先分配共享度更多的资源能够得到更高的资源利用率证明 对于任意一个资源单元( ，) ， ，，其共享度记为 ( ，)扫描检测 中的所有资源单元的共享度，则一定存在一个共享度最小的资源单元，记为( ，) ，其共享度为 ，在其上可分配资源的任务集合为 也必定存在一个共享度是倒数第二小的资源单元，记为( ，) ，其共享度为 ，在其上可分配资源的任务集合为 如果最小共享度的单元存在多个，则任意取其中一个作为共享度最小的资源单元，再从剩余的资源单元中选取一个共享度倒数第二小的单元显然有:可以被分配至资源单元( ，) 的任务集合记为 ，( ) 若优先将 中的任务进行分配，则对先为集合 或者集合 分配资源效果无差异( ) 若优先将 中的任务进行分配，则资源 在当前时刻被 占用假设 占用的时间 中，若其后有 的任务申请资源，不可申请到即 可分配区域选项减若 的当前可分配区域为，则 中的任务需要等待( ) 若优先将 中的任务进行分配由于( ，) 的共享度 ( ，) 的共享度，则一定存在新的资源空间( ，) 可以为 中的任务分配资源所以， 的任务不会因为 的分配而等待综上所述，如果优先分配 中的任务，则可能存在 中的任务需要等待如上证明过程中，集合 仅仅是比集合 共享度略大的任务集合若存在任务集合 ，集合的任务共享度 集合的任务共享度，同理可证上述结论对于任意共享度的任务集合，上述结论均成立算法设计流程根据本文设计的可重构资源分配策略，设计如图 所示的资源分配算法流程图 基于共享度的资源分配算法流程首先根据可重构计算任务的总数已经任务产生的平均频度，选取合适的数值 作为可重构资源分配窗口的大小，与此同时，窗口内的任务集合 也随之确定然后对集合 中的每个任务都分别进行扫描，检测可以将该放置的位置，并形成每个任务可放置的位置集合在扫描每个任务的同时，记录下每个任务进入窗口的时间 ，该时间是以第一个任务进入窗口的时间作为基准时间点，该时间将作为任务分配资源先后的影响因素根据每个任务可放置的位置集合，对 中的所有可用资源位置进行扫描，计算每个可用资源单元的共享度 由每个任务可放置位置集 合 做 并 运 算，形成所有可放置区域的位置集合对可放置区域的位置集合 中的每个单元共享度进行统计分析，按照之前得出的资源分配策略，选取共享度最小的可用资源单元优先进行分配对窗口中的任务选取的原则主要依据两个因素，即该任务占用资源数目的大小和该任务进入窗口的等待时间 如果一个任务占用的资源数目越大，则越应该被优先分配，而如果一个任务在窗口内等待时间越长，也应该被优先分配 按照这一设计原则，本文设计了如下公式所示的任务选取策略，通过公式计算得到每个任务的优先选取权值，权值越高的则将被优先分配资源式中 和分别是对任务的等待时间和占用的资源数两个参数的影响因子，通过对影响因子的调整可以改变这两个参数对任务选取优先情况的影响权值 代表该任务所占资源数测试与分析为了对本文设计的资源分配算法实际性能进行分析，本文构建了实验测试环境，通过软件模拟产生随机的计算任务 通过在 公司的 的芯片进行了模拟测试，测试过程中产生的随机任务都假定为相互之间不存在数据相关，而且每一个任务都完全可以被 中的资源进行加载，即不存在不可加载的任务 所有任务的到达时间也是随机设定的，通过用软件模拟任务的产生过程，对本文设计的 资源分配算法进行了测试 测试过程中主要对 的资源利用率和任务的等待延时两个指标进行测量，以检验本文设计的资源分配算法的总体性能，为了能够对本文设计的算法总体性能有一个对比分析，本文选取了传统的 算法进行对比测试分析，测试结果如图 图 所示图 测试 中不同时刻的资源利用率图 测试 中不同任务的等待时间图 表示的是资源利用率的测试结果 从图中可以看出，采用本文设计的资源分配算法对软件模拟随机产生的任务，其能够确保 中的资源利用率大部分时间介于 之间，这对 的运行而言，是一个比较理想的资源利用率的比值，有利于 各个功能模块的性能发挥，而且从对比分析来看，本文设计的算法对 的资源利用率比传统的 算法得到的资源利用率略高图 表示的是对软件模拟随机产生的任务在等待资源分配过程中的排队延时测试结果，从测试结果来看，随机产生的任务大部分等待延时都在 以内，这表明对软件模拟随机产生的任务大部分时候都能够及时得到资源分配，任务基本上没有额外的分配时间 但是从测试结果也可以看出，有一个时刻任务的等待延时达到了 ，这表明在这一时刻资源分配算法无法及时地对该任务进行分配，该任务只有等待，直到其他正在执行的任务都释放资源 而且通过对 中正在执行的任务进行资源合并，才最终得到了可供当前任务执行的资源空间，因此耗费了较长的等待时间 通过使用模拟软件产生 个随机任务，统计本文设计的资源分配算法的平均等待时间为，而使用 算法的对比测试得到平均等待时间为因此与 算法的对比测试表明，本文设计的资源分配算法其平均等待时间比 算法低 此外，根据文献［］所述的方法对 算法进行改进，按照其描述的基于任务上边界计算最大空闲矩形的算法进行对比测试，使用 同 样 的 个 随 机 任务，测试得到其平均等待时延为 ，比 算法平均等待时延低 由此也表明本文设计的资源分配策略在减少任务平均等待时延方面具有较优的性能综合本文从资源利用率和任务等待延时两个方面的模拟测试结果表明，本文设计的 可重构设计资源分配算法具有较高的实施性，同时也能够较大程度地发挥 中的资源利用率，其总体性能比传统的 算法均更优，尤其是其平均任务等待时间比 算法减少 ，因此该算法更适用于对实时性要求更强的可重构设计应用场合结 语针对 的可重构设计是目前的一个研究热点，但是如何设计高效率的资源分配算法，降低不同任务对 的征用情况，减少可重构任务的平均等待延时，尽可能的提高 的资源利用率，是当前研究的难点［，］，本文提出的基于共享度的 可重构设计资源分配算法，从不同任务队 资源的占用程度进行分析，以同一个资源对多个任务占用的程度作为切入点，较好地解决了 中资源最优分配的解决方案，而且通过证明也论证了本文给出的资源分配策略的较优的一种方案 通过实际模拟的测试表明本文设计的资源分配算法在资源利用率和任务等待延时两方面均优于传统的 算法参 考 文 献［］ ， ，［］， ( ) ， ， :( 下转第 页)通过式( ) 统计出每个细胞核的分割准确率，并绘制盒须图，如图 所示 盒须图是利用数据中的五个统计量: 最小值第一四分位数中位数第三四分位数与最大值来描述数据的一种方法，是统计学中非常有代表性的方法 图 中，蓝色盒子两端边的位置对应数据的上下四分位数，盒子中间的红色线为中位线，这三条线将数据分为 个部分，每一部分代表 数据集 超出须底部的数据为异常值，采用红色点表示 观察该箱须图发现，数据集分布较集中，且 的数据集核分割准确率在以上， 的数据集核分割准确率在 以上， 的数据集核分割准确率在 以上图 全部数据集的分割准确率分布盒须图
　　结 语
　　本文提出了基于颜色分离的免疫组化核分割方法，其优越性在于可对多着色的 图像进行着色分离，进而利用改进的算法直接处理单着色灰度图像，降低了 图像着色不均匀噪声等造成的影响，具有较好的鲁棒性; 另外，算法直接对灰度图像进行聚类，不需要对 各个分量进行迭代，速度较快 实验结果表明，本文算法对免疫组化图像具有较高的分割精度 该方法也适用于其他组织图像，比 如 染 色 图 像 等本文的实验将为临床后续的病理诊断提供定量的分析结果，降低病理医生的主观性造成的诊断偏差，提高诊断效率 由于着色分离的优劣对后续的分割影响较大，而颜色去卷积方法要求图像的背景需为非彩色［］我们下一步将继续研究着色分离的其他方法，探究针对 图像核分割效果更好的方法
    参 考 文 献［］徐平病理诊断中免疫组化技术的应用研究［］中外医疗，( )［］傅蓉免疫组化彩色细胞图像自动分割的研究［］中国医学物理学杂志， ， ， ， 王 慧，江 锋，叶 永 安，等一种新的免疫组化图像分割算法研究［］计算机应用与软件， ( )［］王慧，江锋，叶永安，等基于混合颜色空间的免疫组化图像分割研究［］计算机工程， ( ) ］杨靛青，刘秉瀚，郑智勇基于 模式下淋巴瘤病理彩色图像分割［］福建电脑， ( )［］傅蓉，徐青基于 颜色模型的免疫组化图像分割［］医学信息， ( )［］傅蓉，申洪基于色度学准则分析的免疫组化彩色图像 均值聚类分割 技 术 研 究［］中国体视学与图像分析， ，( ) : 孟丽敏，宋余庆，朱峰基于空间邻域加权的模糊 均值聚类及其应用研究［］计算机应用研究 李枫图像分析中光密度参数物理意义的正确理解和使用［］解剖学杂志， ( )