データ駆動型スケジューリングに基づく大規模並列化の研究

基于数据驱动调度的大规模并行研究

基本信息

批准号：
24680016
负责人：
岸本章宏
金额：
$ 4.49万
依托单位：
Tokyo Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (A)
财政年份：
2012
资助国家：
日本
起止时间：
2012 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-24680016/
关键词：
大規模並列化クラウド組み合わせ問題 DDS

项目摘要

組み合わせ問題を解くメモ化手法の分散並列化は、メモの効率の良い共有の問題のために、高い台数効果を出しにくい。本研究の最終目的は、1000コア以上のCPUを持つスパコン上でも高い性能を発揮できることを研究代表者が示してきた、データ駆動型ワークスケジューリング手法(DDS)を、理論的および実装的な観点から一般化し、様々なメモ化手法を手軽に大規模並列化できるようなDDSライブラリを開発することであった。この目標達成のために、得られた研究成果は次の通りである。まず、プランニングやパズルといった人工知能における典型的な題材を利用して、DDSのスケーラビリティの限界を実験的に徹底的に調査し、DDSの利点・欠点を明らかにした。これによって、DDSライブラリが構築できた際に、性能を予測することの一助につながることが期待できる。次に、DDSにとって重要な対象並列計算機環境である、クラウド環境において、理論的および実験的な成果が得られた。クラウド環境では、計算機資源量と利用時間に基づいて、利用コストが発生するので、DDSを用いるメモリ・インテンシブな並列アルゴリズムは、計算時間だけでなく、利用コストも少なくする必要がある。しかし、最適な利用コストの計算には、並列アルゴリズムが必要とする計算機資源量が既知である必要があり、DDSを用いるメモリ・インテンシブなアルゴリズムでは、一般にこの前提条件は成り立たない。本研究で開発したアルゴリズムでは、必要な利用コストは、最適利用コストの4倍以内で必ず抑えられることを理論的に示し、さらに前述のプランニングやバイオインフォーマティックスで重要な題材であるシーケンスアライメント問題では、ほぼ最適な利用コストで計算できることを実験的に示した。最後に、産業界から高い需要が期待されるスマートグリッドに利用できる「フロンティア法」の共有メモリ環境における並列化を、DDSの特殊ケースとみなせる方法に基づいて行い、有望な初期結果を得た。

由于备忘录的有效共享，难以实现大量设备的备忘录技术的分布平行化。这项研究的最终目的是概括数据驱动的工作调度方法（DDS），研究人员表明，即使从理论和实施的角度来看，它也可以在1,000或更多核心的超级计算机上执行高性能，并从理论和实施的角度来看，并开发了DDS库，从而允许易于大规模地尺度进行各种回忆方法的大规模平行化。为了实现这一目标，获得的研究结果如下：首先，我们使用了人工智能中的典型主题，例如计划和拼图来彻底研究DDS的可伸缩性限制，并发现了DDS的优势和缺点。当可以构建DDS库时，这可以预期有助于预测性能。接下来，在云环境中获得了理论和实验结果，这是对DDS重要的目标平行计算机环境。在云环境中，使用成本是根据计算机资源和使用时间的数量而产生的，因此使用DDS的内存密集型并行算法不仅需要减少计算时间，还需要使用使用成本。但是，已知并行算法所需的计算机资源数量来计算最佳使用成本，并且这种先决条件通常不适合使用DDS的内存密集型算法。该研究理论中开发的算法表明，所需的用法成本始终可以在最佳用法成本的四倍之内保存，并且在实验上，有可能以几乎最佳的使用成本来计算上述序列一致性问题，这是计划和生物信息的重要主题。最后，我们使用可用于智能电网的“边界方法”在共享内存环境中进行并行化，该方法预计该方法将由行业高度要求，基于可以认为是DDS的特殊情况，并实现了有希望的初始结果。