スケジュールナースのブログ

2021年12月17日金曜日

マルチコア時代に性能を出すために

処理を分割して、単純にマルチスレッドにしただけで性能が向上すれば何も問題ないのですが、大抵の場合ボトルネックがあります。それは、各コアのキャッシュに載るかどうかということです。単純に参照データがコアキャッシュ内に載れば何も問題はありません。その場合は、ほぼCPUコア倍に性能の向上が期待できます。問題は、載り切らない場合どうするか？ということです。その場合は、

１）なんとかして、データ圧縮する

２）シーケンシャルアクセスしかないようにする

の何れかの方法を取る必要があります。シーケンシャルアクセスしかほぼないのならば、数GBのデータであってもキャッシュは効きます。Simplexのマルチコア化が難しいのは、大規模インスタンスになると２）が難しくなるからだと思います。

シングルコア性能が頭打ちの時代ですが、より速く答えを出すというソルバに求められることは変わりません。未来永劫変わらない普遍的な要求だと思います。

2021年12月16日木曜日

Instance22世界記録更新

ようやく満足できる解が見つかったので承認申請しました。 Ryzen８cores　開発中のAlgorithm3で46992secかかりました。Search Spaceが10の18953乗です。最適解証明はできませんでした。

Instance22　LB:30240　UB:30244

2021年12月15日水曜日

Instance22世界記録更新

UB:31161⇒30441　

に更新しました。未だ途中経過なので承認申請していません。（チューニングしながら行っており更新したらコード修正⇒再トライを行っています。）

2021年12月14日火曜日

AVX2は、自作の Interior Point Methodを使っています。通常は、Simplexの雄CLPを使うのですが、大規模インスタンスINRC2 n0120w8 や、SchedulingBenchmarks Instance21以上では、Simplexより内点法の方が速度的に有利です。そのために切り替えていますが、万が一AVX2をサポートしないCPUであった場合に落ちてしまいます。通常の実務インスタンスで、この規模はほぼないと言えますが、Githubに上げるプロジェクトを駆動する場合もあるでしょう、そういった対策の意味で、CPUがAVX2をサポートしているかどうかを知る必要がありました。ありがたく、下記を使わせて頂いております。

https://gitlab.com/yoshimoto/cpuid/-/blob/master/cpuid.cpp

2021年12月13日月曜日

Instance22世界記録更新　By Algorithm3

更新しましたが、未だ途中経過なので承認申請はしていません。

UB:31279⇒３１１６１(Search Spaceがまた前回(Instance21)から上がって、１０の18953乗になっています。）

今回は、Algorithm3によるソルバでの途中経過です。Algroritm3は、Near Optimalなアルゴリズムで、基本的に厳密解を保証しません。厳密解アルゴリズムは、Algorithm4ですが、今までの評価では、Algorithm3がAlgorithm4に精度的に劣るケースは発見されていません。また、Algorithm4では、instance21以上では、実質的にコンパイル不可能ですが、Algorithm3では、(解けるかどうかは別にして)コンパイルは可能です。また、実務的インスタンス、例えば池上ベンチマークもAlgorithm4ではコンパイルできませんが、Algorithm３では問題なくコンパイル可能です。まとめると、

Algorithm1：SAT系ソルバ

Algorithm4 :数理的ソルバ　(コンパイル出来れば)速い　厳密解探索用、コンパイル出来ないことがある。

Algorithm3 :数理的ソルバ　汎用　Near Optimal。 Algorithm1で時間がかかる場合、精度と速度で有利（ソフト制約が多数かつ多数のソフトエラーが残る場合）。また長大規模(3ヶ月以上）または、大規模(100人以上)でも、Algoritm1より有利になります。コンパイル出来ないことはないことを目指している。(しかし、経験的に枯れたAlgorithm1レベルになるには１年以上必要）

CPUコア数が、多くなればなるほど、Algorithm3は有利となります。また、この条件下での学術ベンチマークでは、Gurobi/Cplex、AutoRoster含め他のソルバを圧倒します。

現在、Algorithm3についてベンチマークの評価とチューニング作業中です。

実務インスタンスについては、シフト系については、実装を完了していますが、タスク系については、未だ実装していません。また、ペア制約も現在実装未です。

2021年12月11日土曜日

量子アニーリングについて

組み合わせ最適化は、ナーススケジューリングを包括する広範囲な問題領域です。

「量子」と組合せ最適化に関する怪しい言説 ―とある研究者の小言― - むしゃくしゃしてやった，今は反省している日記 (hatenablog.com)

それでは、古典的数理的解法で、ナーススケジューリング問題はどこまで解けているか？ということを少し論じてみたいと思います。

ナーススケジューリングの黎明期は、メタヒューリスティクスによる解法が主で、タブサーチ等が用いられました。

その後、MIPソルバーの発展によって、Gurobi・Cplexを始めとする数理的ソルバは、従来の解を更新、なおかつ、そのうちの超大規模を除く殆どを厳密解として提示出来るようになりました。(INRC1・SchedulingBenchmarks)　

そこで、INRC2では、問題をより大規模にして、なおかつ問題を複雑にしてMIPソルバーでは解きにくい形態としています。実際、INRC2問題は、MIPソルバーでは、殆ど解けていません。（実インスタンス形態としては、インスタンスによるのですが、どちらかというと、INRC2に近い実感があります。）

現在、MIPソルバーで、かなり解けるようにはなったけれども、全てが解ける訳ではありません。また、MIPソルバー間、AutoRoster等のナーススケジューリングソルバ間でも、性能の差がある、というのが現在地になります。

それでは、StateOfArtのソルバで、一体どこまで解けているか？という問いに対する回答が、スケジュールナースⅢになります。

現在、スケジュールナースⅢでの数理的解法結果を一連のベンチマークとしてデータを採取中です。実務問題については、未だ課題が山積していますが、少なくともベンチマークについては、動いており現在公開に向けバージョンアップしたバージョンAlgorithm3としてチューニング準備中です。ちなみにAlgorithm2は、MIPソルバそのもので、10人以下でしたらそこそこ動きますが、あくまで商用でないMIPソルバだとこんなもんです、程度で殆ど実用的ではありません。Algorithm1は、従来通りで変わりません。Algorithm4は、バージョンアップしていますがAlgorithm3の特殊形態です。Algorithm3は、汎用化した数理的ソルバです。

Algorithm3が、ナーススケジューリング問題の古典的解法によるStateOfArtと言い切ってよいと思います（GurobiでもCplexでもなく）。

一つ指摘しておきたいことは、必ずしもMIPソルバが全能ということではなく、これは容易に解けるだろうと思われる小さな問題でも、MIPソルバで解けなかったり、意外に時間がかかる事例が散見されることです。例えば　

Benchmarks | What is Schedule NurseⅢ (nurse-scheduling-software.com)

で、GPost/GPostB,BCDT-Sep,WHPP,Valouxis-1、ikegami-3Shiftxx 等です。これらは、人工的・機械的にベンチマーク用として造られたものではなく、実務問題をモデリングしていることにご注意ください。GPostは、僅か8人ですが、数理的に解くのは難しい部類にはいります。

ベンチマークは、アカデミック上の特定の実装が有利に働くような意図が背景にあり、必ずしも実問題にマッチしていません。実務問題とは基本的に異なりますが、INRC2に関しては、シフト形態は別にしてほどよくハード・ソフト制約がブレンドされ実務用途に近いと思います。

どのようなインスタンスでも安定して、短時間にNear Optimal(Ex.30sec/1min) 、時間をかければ厳密解に到達できることが、ソルバに求められる要件です。

いずれにせよ、今後はスケジュールナースⅢが一つの指標になると言い切ってよいと思います。

2021年12月2日木曜日

CPU使用率計測

思ったように超大規模でのマルチスレッドの性能が出ないので、CPU使用率をタスクマネージャではなく、ソルバ上で得ようと思いました。中々良いコードが見当たらなかったのですが、StackOverflowにありました。Windows用です。

#pragma once
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include "pdh.h"

#pragma comment(lib, "pdh.lib")

class Query {

    PDH_HQUERY cpuQuery;
    PDH_HCOUNTER cpuTotal;
public:
    Query() {
        PdhOpenQuery(NULL, NULL, &cpuQuery);
        PdhAddCounter(cpuQuery, TEXT("\\Processor(_Total)\\% Processor Time"), NULL, &cpuTotal);
        PdhCollectQueryData(cpuQuery);
    }

    operator double() {
        PDH_FMT_COUNTERVALUE counterVal;

        PdhCollectQueryData(cpuQuery);
        PdhGetFormattedCounterValue(cpuTotal, PDH_FMT_DOUBLE, NULL, &counterVal);
        return counterVal.doubleValue;
    }
};

使い方は、簡単です。omp forループ後に、

Query q;

cout << q << "[%]" <<endl;

で表示されます。

登録: 投稿 (Atom)