[WC2001]高性能计算机 解题报告

高性能计算机

hpc.pas(exe)

hpc.in

hpc.out

【问题描述】

现在有一项时间紧迫的工程计算任务要交给你——国家高性能并行计算机的主管工程师——来完成。为了尽可能充分发挥并行计算机的优势，我们的计算任务应当划分成若干个小的子任务。

这项大型计算任务包括A和B两个互不相关的较小的计算任务。为了充分发挥并行计算机的运算能力，这些任务需要进行分解。研究发现，A和B都可以各自划分成很多较小的子任务，所有的A类子任务的工作量都是一样的，所有的B类子任务也是如此（A和B类的子任务的工作量不一定相同）。A和B两个计算任务之间，以及各子任务之间都没有执行顺序上的要求。

这台超级计算机拥有p个计算节点，每个节点都包括一个串行处理器、本地主存和高速cache。然而由于常年使用和不连贯的升级，各个计算节点的计算能力并不对称。一个节点的计算能力包括如下几个方面：

1.      就本任务来说，每个节点都有三种工作状态：待机、A类和B类。其中，A类状态下执行A类任务；B类状态下执行B类任务；待机状态下不执行计算。所有的处理器在开始工作之前都处于待机状态，而从其它的状态转入A或B的工作状态（包括A和B之间相互转换），都要花费一定的启动时间。对于不同的处理节点，这个时间不一定相同。用两个正整数t^A_i和t^B_i (i=1,2,…,p)分别表示节点i转入工作状态A和工作状态B的启动时间（单位：ns）。

2.      一个节点在连续处理同一类任务的时候，执行时间——不含状态转换的时间——随任务量（这一类子任务的数目）的平方增长，即：
若节点i连续处理x个A类子任务，则对应的执行时间为
t=k^A_ix²
类似的，若节点i连续处理x个B类子任务，对应的执行时间为：
t=k^B_ix²
其中，k^A_i和k^B_i是系数，单位是ns。i=1,2,…,p。

任务分配必须在所有计算开始之前完成，所谓任务分配，即给每个计算节点设置一个任务队列，队列由一串A类和B类子任务组成。两类子任务可以交错排列。

计算开始后，各计算节点分别从各自的子任务队列中顺序读取计算任务并执行，队列中连续的同类子任务将由该计算节点一次性读出，队列中一串连续的同类子任务不能被分成两部分执行。

【编程任务】

现在需要你编写程序，给这p个节点安排计算任务，使得这个工程计算任务能够尽早完成。假定任务安排好后不再变动，而且所有的节点都同时开始运行，任务安排的目标是使最后结束计算的节点的完成时间尽可能早。

【输入输出】

输入文件名是hpc.in。

文件的第一行是对计算任务的描述，包括两个正整数n_A和n_B，分别是A类和B类子任务的数目，两个整数之间由一个空格隔开。

文件的后面部分是对此计算机的描述：

文件第二行是一个整数p，即计算节点的数目。

随后连续的p行按顺序分别描述各个节点的信息，第i个节点由第i+2行描述，该行包括下述四个正整数（相邻两个整数之间有一个空格）：

t^A_i  t^B_i  k^A_i  k^B_i

输出文件名是hpc.out。其中只有一行，包含有一个正整数，即从各节点开始计算到任务完成所用的时间。

【样例】

设输入文件hpc.in为

5 5

3

15 10 6 4

70 100 7 2

30 70 1 6

对应的输出文件hpc.out为

           93

【数据说明】

1≤n_A≤60，1≤n_B≤60

1≤p≤20

1≤t_B≤1000，1≤t_B≤1000，1≤k_A≤50，1≤k_B≤50

【解析】

       首先明确题意：一旦开始工作，一个计算节点不可以转入待机状态，除非执行完所以任务。

       对于最大值最小这样的问题，一般的思路为二分答案，但对于冬令营的试题，这种一般思路显然是行不通的。主要问题在于，对于一个计算节点，连续执行同一种任务并不是最优情况，以本题的样例为例，如果令节点2处理2个A类子任务，3个B类子任务，按照A->A->A->B->B->B的顺序执行耗时115ns，而按照A->A->B->B->A->B的顺序执行耗时为100ns。这样，即使我们通过二分答案确定了某个值，检验它是否可行仍然需要使用动态规划，倒不如直接使用动态规划求解。

       我们首先预处理每个计算节点处理连续x个A或B类子任务的耗时，即设timeA[i][j]为第i给计算节点处理连续j个A类子任务的总耗时（包括切换时间），timeB的意义与之类似。实现如下：

for (int i = 0; i<n; i++)

{

    for (int j = 1; j <= sumA; j++)

    {

        timeA[i][j] = computer[i].tA + computer[i].kA*j*j;

    }

    for (int j = 1; j <= sumB; j++)

    {

        timeB[i][j] = computer[i].tB + computer[i].kB*j*j;

    }

}

       设dp1[i][j][k]为第i个计算节点处理j个A类子任务和k个B类子任务的最短耗时。对于每个状态dp1[i][j][k],我们可以枚举切换的位置以获得最优解，过程与区间dp合并区间的方式有些类似。但这样存在一个问题：我们无法确定转移时的上一个状态最后一个执行的子任务是A类还是B类，因此我们需要一个额外的维度表示最后一个执行的子任务的类型。

       设dp2[i][j][k]表示前i个计算节点处理j个A类子任务和k个B类子任务的最短耗时。状态转移的方式与dp1类似，对于每个状态dp2[i][j][k]，我们需要遍历dp2[i-1][j][k]，找到最佳的转移位置。

       【参考程序】

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#define INF 0x3F3F3F3F

using namespace std;

void read(int &x)

{

    x = 0; char ch = getchar(); bool f = 0;

    while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }

    while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }

    if (f)x = -x;

}

void read(long long &x)

{

    x = 0; char ch = getchar(); bool f = 0;

    while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }

    while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }

    if (f)x = -x;

}

int sumA, sumB;

int n;

struct

{

    int tA, tB, kA, kB;

}computer[20];

int timeA[20][61], timeB[20][61];

int dp1[20][61][61][2], dp2[20][61][61];

int main()

{

    read(sumA); read(sumB);

    read(n);

    for (int i = 0; i<n; i++)

    {

        read(computer[i].tA);

        read(computer[i].tB);

        read(computer[i].kA);

        read(computer[i].kB);

    }

    for (int i = 0; i<n; i++)

    {

        for (int j = 1; j <= sumA; j++)

        {

            timeA[i][j] = computer[i].tA + computer[i].kA*j*j;

        }

        for (int j = 1; j <= sumB; j++)

        {

            timeB[i][j] = computer[i].tB + computer[i].kB*j*j;

        }

    }

    for (int i = 0; i<n; i++)

    {

        for (int j = 0; j <= sumA; j++)

        {

            for (int k = 0; k <= sumB; k++)

            {

                //假设只进行一次切换，将其作为状态的初始值

                //但应注意，若j=0,dp[i][j][k][0]=INF，笔者因为这个问题调试了近1小时

                if (j != 0)dp1[i][j][k][0] = timeA[i][j] + timeB[i][k];

                else dp1[i][j][k][0] = INF;

                if (k != 0)dp1[i][j][k][1] = timeA[i][j] + timeB[i][k];

                else dp1[i][j][k][1] = INF;

                for (int j0 = 1; j0 <= j; j0++)

                {

                   dp1[i][j][k][0] = min(dp1[i][j][k][0], dp1[i][j - j0][k][1] + timeA[i][j0]);

                }

                for (int k0 = 1; k0 <= k; k0++)

                {

                   dp1[i][j][k][1] = min(dp1[i][j][k][1], dp1[i][j][k - k0][0] + timeB[i][k0]);

                }

            }

        }

    }

    for (int j = 0; j <= sumA; j++)

    {

        for (int k = 0; k <= sumB; k++)

        {

            dp2[0][j][k] = min(dp1[0][j][k][0], dp1[0][j][k][1]);

        }

    }

    for (int i = 1; i<n; i++)

    {

        for (int j = 0; j <= sumA; j++)

        {

            for (int k = 0; k <= sumB; k++)

            {

                dp2[i][j][k] = INF;

                for (int j0 = 0; j0 <= j; j0++)

                {

                   for (int k0 = 0; k0 <= k; k0++)

                   {

                       dp2[i][j][k] = min(dp2[i][j][k], max(dp2[i - 1][j0][k0], min(dp1[i][j - j0][k - k0][0], dp1[i][j - j0][k - k0][1])));

                   }

                }

            }

        }

    }

    cout << dp2[n - 1][sumA][sumB] << endl;

    return 0;

}