N-задания на M-машинах с графиком приоритета и разным временем выполнения

Question

N-задания на M-машинах с графиком приоритета и разным временем выполнения

Предположим, у меня есть n рабочих мест и m машин. У заданий есть ограничения приоритета (заданные в ориентированном ациклическом графе) и разное время выполнения. Расписание НЕ должно быть упреждающим. Какой алгоритм лучше всего их планировать? Какие-либо предложения? Я знаю, что в целом это NP-сложно, поэтому эвристика тоже подходит. Я бы рассмотрел расписание уровней Ху, приведенное здесь http://web.cecs.pdx.edu/~mperkows/temp/0002.scheduling2.pdf, но, если я правильно понимаю, оно предполагает одинаковое время выполнения.

2

algorithm parallel-processing job-scheduling parallelism-amdahl occam-pi

Источник

user11837685 03 сен '19 в 18:03

2 ответа

Другие вопросы по тегам algorithm parallel-processing job-scheduling parallelism-amdahl occam-pi

user585411 03 сен '19 в 19:27 2019-09-03 19:27 · Answer 1 · 2019-09-03 19:27

Я бы предложил жадную эвристику.

Предположим, что у вашей работы есть execution_timeи дети. Пустьdependency_time быть execution_time для листовых работ и execution_time + max(dependency_time for children) для других работ.

На каждом этапе планируйте доступную работу с наибольшим dependency_time.

user3666197 04 сен '19 в 18:25 2019-09-04 18:25 · Answer 2 · 2019-09-04 18:25

_{Представлено в глубоком восхищении людей InMOS и для удовольствия решателей и деятелей, которые могут вдохновляться на всю оставшуюся жизнь :o)}

Пример решения: ^{использовался спутником Джотто ЕКА для полета в глубокий космос... Комета Галлея}

Пионер проф. CAR Hoare новый, детерминированный (если только внешние события / стимулы /ALTв настоящее время) для решения проблем параллелизма стало возможным планирование.

На основе планирования, основанного на π-исчислении, π-алгебра решает зависимости дляN-работа на M-ресурсы с учетом зависимостей DAG и допускают как переменную длительность задания, так и взаимодействие между процессами (с использованием новаторской техники разделения заданий, поддержания их парного соединения с дешевыми, быстрыми и эксклюзивными CSP-каналами, если они существуют, для обмена фрагменты информации в все еще детерминированной и запланированной неразрушающей манере)

 ::: occam-pi executed all the N-jobs as per dependencies were specified
 :::                   using pi-calculus algebra for deterministic
 :::                   scheduling N-jobs over a pool of M-resources available
 :::                   w.r.t. all dependencies
 ::: 
 job:   1      job duration:    15 timer:  545252301 START.... __
 job:  11      job duration:     9 timer:  545252302 START.... __
 job:  11      job duration:     9 timer:  545252317 FINISH... __
 job:  21      job duration:     8 timer:  545252447 START.... __
 job:  21      job duration:     8 timer:  545252489 FINISH... __
 job:  20      job duration:    16 timer:  545252447 START.... __
 job:  20      job duration:    16 timer:  545252538 FINISH... __
 job:  19      job duration:     7 timer:  545252447 START.... __
 job:  19      job duration:     7 timer:  545252614 FINISH... __
 job:  12      job duration:     9 timer:  545252447 START.... __
 job:  12      job duration:     9 timer:  545252659 FINISH... __
 job:  13      job duration:     8 timer:  545252682 START.... __
 job:  13      job duration:     8 timer:  545252704 FINISH... __
 job:  14      job duration:     7 timer:  545252727 START.... __
 job:  14      job duration:     7 timer:  545252752 FINISH... __
 job:  15      job duration:     6 timer:  545252775 START.... __
 job:  15      job duration:     6 timer:  545252798 FINISH... __
 job:  16      job duration:     5 timer:  545252819 START.... __
 job:  16      job duration:     5 timer:  545252840 FINISH... __
 job:  17      job duration:     4 timer:  545252862 START.... __
 job:  17      job duration:     4 timer:  545252886 FINISH... __
 job:  18      job duration:     9 timer:  545252908 START.... __
 job:  18      job duration:     9 timer:  545252930 FINISH... __
 job:   8      job duration:     2 timer:  545252301 START.... __
 job:   8      job duration:     2 timer:  545252976 FINISH... __
 job:   9      job duration:     5 timer:  545252999 START.... __
 job:   9      job duration:     5 timer:  545253022 FINISH... __
 job:  10      job duration:    31 timer:  545253044 START.... __
 job:  10      job duration:    31 timer:  545253093 FINISH... __
 job:   1      job duration:    15 timer:  545252416 FINISH... __
 job:   5      job duration:    31 timer:  545253142 START.... __
 job:   5      job duration:    31 timer:  545253230 FINISH... __
 job:   6      job duration:    27 timer:  545253242 START.... __
 job:   6      job duration:    27 timer:  545253309 FINISH... __
 job:   7      job duration:    11 timer:  545253324 START.... __
 job:   7      job duration:    11 timer:  545253347 FINISH... __
 job:   4      job duration:    12 timer:  545253141 START.... __
 job:   4      job duration:    12 timer:  545253392 FINISH... __
 job:   2      job duration:    24 timer:  545253141 START.... __
 job:   2      job duration:    24 timer:  545253436 FINISH... __
 job:   3      job duration:     6 timer:  545253460 START.... __
 job:   3      job duration:     6 timer:  545253482 FINISH... __

Эта main() использовал пример зависимостей, определенных DAG для~ 21-работы переменной продолжительности, выполняемые в режиме онлайн:

PROC main(CHAN BYTE keyboard, screen, error)

  [25]CHAN messagePROTOCOL mon :
  CHAN     messagePROTOCOL prn :

  PAR   -- DAG-root-node-(sorry for naive ASCII-art)-*-*-*-*-* DAG root-node's subtree(s)
    --                                               | | | | |
    SysPrintr(screen!, prn?)-------------------------+ | | | |
    --                                                 | | | |
    SysMonMUX(   prn!, mon?)---------------------------+ | | |
    --                                                   | | |
    SEQ -- ----------------------------------------------: | |
      --                                                 | | |
      job(      1, 15, mon[ 1]!)   --job_1---------------+ | |
      --                                                 | | |
      PAR ----------------------------------------+-+-+--* | |
        --                                        | | |    | |
        job(    4, 12, mon[ 4]!)   --     job_4---+ | |    | |
        --                                          | |    | |
        SEQ ----------------------------------------: |    | |
          --                                        | |    | |
          job(  2, 24, mon[ 2]!)   --     job_2-----+ |    | |
          job(  3,  6, mon[ 3]!)   --          _3---+ |    | |
        SEQ ------------------------------------------:    | |
          job(  5, 31, mon[ 5]!)   --     job_5-------+    | |
          job(  6, 27, mon[ 6]!)   --          _6-----+    | |
          job(  7, 11, mon[ 7]!)   --            _7---+    | |
    SEQ ---------------------------------------------------: |
      --                                                   | |
      job(      8,  2, mon[ 8]!)   --job_8-----------------+ |
      job(      9,  5, mon[ 9]!)   --     job_9------------+ |
      job(     10, 31, mon[10]!)   --          job_10------+ |
    SEQ -----------------------------------------------------:
      --                                                     |
      job(     11,  9, mon[11]!)   --job_11------------------+
      PAR ---------------------------------------------------*---*-*-*-*
        --                                                       | | | |
        job(   21,  8, mon[21]!)   --      job_21----------------+ | | |
        job(   20, 16, mon[20]!)   --      job_20----------------|-+ | |
        job(   19,  7, mon[19]!)   --      job_19----------------|-|-+ |
        SEQ -----------------------------------------------------------:
          --                                                           |
          job( 12,  9, mon[12]!)   --      job_12----------------------+
          job( 13,  8, mon[13]!)   --            _13-------------------+
          job( 14,  7, mon[14]!)   --               _14----------------+
          job( 15,  6, mon[15]!)   --                  _15-------------+
          job( 16,  5, mon[16]!)   --                     _16----------+
          job( 17,  4, mon[17]!)   --                        _17-------+
          job( 18,  9, mon[18]!)   --                           _18----+
: -- main() ------------------------------------------------------------

Код можно запустить онлайн на сайте Try-it-Online, чтобы получить любую радость от экспериментов с настоящими[PARALLEL] проектирование системы - единственная неприятность заключается в том, что InMOS Transputers были заменены ядром (ядрами) процессора x86 на их платформе с ограниченными возможностями для "более дикого" PAR-разделы.

Наслаждайтесь дальнейшим взломом планирования на основе π-исчисления:

#INCLUDE "course.module"                  -- #USE "course.lib"

--                      +------+--------+----+----------+
--                      | jobID|duration|time|aSTRING[] |
--      +---------------+------+--------+----+----------+
--      |messagePROTOCOL|   INT;     INT; INT; [10]BYTE |
PROTOCOL messagePROTOCOL IS INT;     INT; INT; [10]BYTE : -- Error-occ21-.code.tio.occ(7)- array type must have dimension specified
--      +---------------+------+--------+----+----------+

PROC job ( VAL INT id, VAL INT duration, CHAN messagePROTOCOL outP )

  INT               t  :                   -- declare INT
  TIMER aCentralCLOCK  :                   -- declare TIMER
  [10]BYTE  flag.START :                   -- declare [10]BYTE
  [10]BYTE  flag.FINISH:                   -- declare [10]BYTE

  SEQ ------------------------------------------------------------------SEQ:
    flag.START  := " START...."                                         -- .SET
    flag.FINISH := " FINISH..."                                         -- .SET

    aCentralCLOCK ?      t                                              -- .read ? .SET t from timer at start
    outP ! id; duration; t; flag.START                                  -- .outP ! messagePROTOCOL{ id; duration; t; aString }

    aCentralCLOCK ? AFTER ( t PLUS duration )                           -- .read ? .wait  till ( start PLUS duration )
    --              ^^^^^                                               
    --              |||||                                               
    --              |||||                                               
    --              +++++------------------------------------------------- <this> emulates a variable <job>-duration

    aCentralCLOCK ?      t                                              -- .read / .SET t from timer at finish
    outP ! id; duration; t; flag.FINISH                                 -- .outP ! messagePROTOCOL{ id; duration; t; aString }
: -- job() -------------------------------------------------------------

PROC SysPrintr(CHAN BYTE outCH, CHAN messagePROTOCOL inCH )

  INT      iJobID   :
  INT      iDuration:
  INT      iTimer   :
  [10]BYTE aString  :

  WHILE TRUE
    SEQ
      --GET ? ----------------------------------------------------------
      inCH  ? iJobID; iDuration; iTimer; aString
      --PRINT ---------------------------outCH--------------------------
      out.string(   " job: ",         5, outCH )
      out.int(       iJobID,          3, outCH )

      out.string( " job duration: ", 20, outCH )
      out.int(         iDuration,     5, outCH )

      out.string( " timer: ",         8, outCH )
      out.int(     iTimer,           10, outCH )

      SEQ i = 0 FOR SIZE aString
        outCH ! aString[i]

      out.string(     "__*n",         4, outCH )
      flush(                             outCH )                        -- .flush
: -- SysPrintr() -------------------------------------------------------

PROC SysMonMUX(CHAN messagePROTOCOL out!, []CHAN messagePROTOCOL in?)
  INT      iJobID   :
  INT      iDuration:
  INT      iTimer   :
  [10]BYTE aString  :

  WHILE TRUE
    ALT
      in[ 0] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[ 1] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[ 2] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[ 3] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[ 4] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[ 5] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[ 6] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[ 7] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[ 8] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[ 9] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[10] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[11] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[12] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[13] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[14] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[15] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[16] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[17] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[18] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[19] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[20] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[21] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
      in[22] ? iJobID; iDuration; iTimer; aString
        out  ! iJobID; iDuration; iTimer; aString
: -- SysMonMUX()--------------------------------------------------------

PROC main(CHAN BYTE keyboard, screen, error)

  [25]CHAN messagePROTOCOL mon :
  CHAN     messagePROTOCOL prn :

  PAR   -- DAG-root-node ----------------------------*-*-*-*-* DAG root-node's subtree(s)
    --                                               | | | | |
    SysPrintr(screen!, prn?)-------------------------+ | | | |
    --                                                 | | | |
    SysMonMUX(   prn!, mon?)---------------------------+ | | |
    --                                                   | | |
    SEQ -- ----------------------------------------------: | |
      --                                                 | | |
      job(      1, 15, mon[ 1]!)   --job_1---------------+ | |
      --                                                 | | |
      PAR ----------------------------------------+-+-+--* | |
        --                                        | | |    | |
        job(    4, 12, mon[ 4]!)   --     job_4---+ | |    | |
        --                                          | |    | |
        SEQ ----------------------------------------: |    | |
          --                                        | |    | |
          job(  2, 24, mon[ 2]!)   --     job_2-----+ |    | |
          job(  3,  6, mon[ 3]!)   --          _3---+ |    | |
        SEQ ------------------------------------------:    | |
          job(  5, 31, mon[ 5]!)   --     job_5-------+    | |
          job(  6, 27, mon[ 6]!)   --          _6-----+    | |
          job(  7, 11, mon[ 7]!)   --            _7---+    | |
    SEQ ---------------------------------------------------* |
      --                                                   | |
      job(      8,  2, mon[ 8]!)   --job_8-----------------+ |
      job(      9,  5, mon[ 9]!)   --     job_9------------+ |
      job(     10, 31, mon[10]!)   --          job_10------+ |
    SEQ -----------------------------------------------------*
      --                                                     |
      job(     11,  9, mon[11]!)   --job_11------------------+
      PAR ---------------------------------------------------*---*-*-*-*
        --                                                       | | | |
        job(   21,  8, mon[21]!)   --      job_21----------------+ | | |
        job(   20, 16, mon[20]!)   --      job_20----------------|-+ | |
        job(   19,  7, mon[19]!)   --      job_19----------------|-|-+ |
        SEQ -----------------------------------------------------------+
          --                                                           |
          job( 12,  9, mon[12]!)   --      job_12----------------------+
          job( 13,  8, mon[13]!)   --            _13-------------------+
          job( 14,  7, mon[14]!)   --               _14----------------+
          job( 15,  6, mon[15]!)   --                  _15-------------+
          job( 16,  5, mon[16]!)   --                     _16----------+
          job( 17,  4, mon[17]!)   --                        _17-------+
          job( 18,  9, mon[18]!)   --                           _18----+
: -- main() ------------------------------------------------------------

Кредит: благодарность bazza за напоминание об этой памятной космической миссии оккам-пи

N-задания на M-машинах с графиком приоритета и разным временем выполнения

2 ответа

Пример решения: использовался спутником Джотто ЕКА для полета в глубокий космос... Комета Галлея

Пример решения: ^{использовался спутником Джотто ЕКА для полета в глубокий космос... Комета Галлея}