Изменение вектора прерывания

MS-DOS предоставляет две функции 35h и 25h прерывания 21h для чтения и установки вектора прерывания.

Функция 35h

Выполняет чтение адреса подпрограммы обработки прерывания.

· Вызов:

ah = 35h

al = номер прерывания

· Возвращаемое значение:

es:bx – указатель на подпрограмму прерывания

· Примечание. Функция получает адрес, указанного AL прерывания из таблицы векторов прерываний. BX содержит смещение, а ES сегмент адреса подпрограммы.

Пример.

mov ah, 35h ; номер функции

mov al, 21h ; номер прерывания

int 21h

В результате: (BX) = 048B, (ES) = 0DDE.

Функция 25h

Выполняет занесение нового вектора прерывания.

· Вызов:

ah = 25h

al = номер прерывания

ds:dx – указатель на подпрограмму обработки прерывания

· Возвращаемое значение:

Нет

· Примечание. Функция устанавливает адрес прерывания, указанного в al в таблицу векторов прерываний. dx содержит смещение, а ds сегмент устанавливаемой подпрограммы.

Дополнительные сведения о структуре DOS и BIOS

Прямое обращение к видеопамяти

Видеопамять компьютера любой конфигурации расположена в адресном пространстве оперативного запоминающего устройства (ОЗУ). Это позволяет напрямую адресовать видеопамять одним из косвенных способов адресации памяти. Видеопамять занимает адреса с A000h по BFFFh, что составляет 128 Кбайт. Для увеличения объёмов видеопамяти (до 64 Мбайт), она делиться на слои, так что по одному адресу находиться несколько ячеек, которые расположены в разных слоях. Обращение к видеопамяти зависит от видеорежима, который определяет количество точек по горизонтали и вертикали, а так же количество битов, отводимую для хранения кода цвета каждой точки. Графическими режимами управляет видеоадаптер.

Более простым для программирования, допускающим простой доступ к видеопамяти, является символьный режим, который мы и рассмотрим подробнее. Для работы в символьном режиме отводится 16 Кбайт памяти, начиная с адреса B800h. Экран делится на 80 столбцов и 25 строк. Общее количество знакомест 80 х 25= 2000. Для каждого знакоместа в видеопамяти отводится два байта: чётный байт – ASCII код символа, нечётный – байт атрибутов. Счёт строк и колонок идёт из верхнего левого угла экрана, в байте b800h:0000h хранится символ выводящийся в нулевой строке и нулевой колонке, в байте b800h:0001h хранится атрибут этого символа. В байте b800h:0002h хранится символ выводящийся в нулевой строке и первой колонке, в байте b800h:0002h хранится атрибут этого символа и т.д.

Байт атрибутов имеет следующую структуру:

	Фон	Символ
Атрибут	BL	R	G	B	I	R	G	B
Номер бита

BL	–	признак мерцания;		R	–	красный цвет;
G	–	зелёный цвет;		B	–	синий цвет;
I	–	Интенсивность свечения.

Для доступа к видеопамяти в текстовом режиме можно использовать непосредственно один из сегментных регистров, например, ES:

mov ax, 0b800h ; записать в регистр

mov es, ax ; es адрес начала видеопамяти

xor bx, bx ; смещение символа от начала видеопамяти

mov dh, 00010100b ; атрибуты: на голубом фоне красный символ

mov dl, 65h ; ASCII код символа

mov word ptr es:[bx], dx ; запись в видеопамять символа и атрибута

inc bx ; смещение для

inc bx ; следующего символа

Другой способ доступа – размещение сегмента данных фиксировано, в области видеопамяти директивой AT.

video segment AT 0b800h

CHAR_ATRIB db 4000 dup(?)

video ends

code segment

assume cs: code, ds:video

START: mov ax, video

mov ds, ax

xor si, si

mov dl, byte ptr CHAR_ATRIB[si] ;чтение символа

inc si

mov dh, byte ptr CHAR_ATRIB[si] ;чтение атрибута

. . .

Буфер клавиатуры

В ОЗУ, начиная с адреса 0040h, находится область данных BIOS, в которой хранится различная системная информация: адреса портов устройств, количество тиков таймера, начиная с полуночи и т.д. В частности, в этой области организован буфер клавиатуры, который способен принять до 15 символов от клавиатуры. Исполняемая программа должна опрашивать этот буфер и извлекать из него символы, иначе буфер переполнится, о чём свидетельствует писк встроенного динамика при нажатии очередной клавиши.

Буфер организован как круговой массив, т.е. при достижении конца буфера, он, если возможно начинает заполняться сначала. Два указателя: "голова" и "хвост" определяют состояние буфера. "Голова" показывает на первую свободную ячейку буфера, куда записывается очередной символ, поступивший от клавиатуры. "Хвост" показывает символ, который будет прочитан исполняемой программой при очередном обращении к буферу. Если буфер пуст, оба указателя показывают на одну и ту же ячейку буфера. Адрес "головы" буфера находится по адресу word ptr 0040h:001ah, а адрес "хвоста" по адресу word ptr 0040h:001ch. Если содержимое обоих указателей совпадает, значит клавиши нажаты не были. Эту проверку можно использовать для вызова в программе функции, читающей символ из буфера клавиатуры.

Пример выполнения работы

Написать программу на ассемблере, выводящую в текущее положение курсора символ @. Следующий символ @ выводить в позицию выше, ниже, левее или правее текущего символа, в зависимости от нажатия клавиш “8”, “2”, “4”, “6” на цифровой клавиатуре. Вывод осуществлять непрерывно с некоторой задержкой. Нажатие клавиши “0” завершает выполнение программы.

· Примечание. В программе необходимо вести отсчёт времени для задержки вывода символа @. Для этого необходимо изменить подпрограмму обработки прерывания от таймера 08h. Так как эта подпрограмма выполняет важные операции по управлению компьютером, для получения временного интервала используется прерывание 1Ch. Это прерывание вызывается из подпрограммы обработки прерывания 08h и содержит только команду iret. Предназначено оно специально для пользовательских программ, которым необходимо следить за интервалами отсчёта таймера.

Текст программы

data segment

DIRECT db 1 ; направление перемещения

EXIT db 0 ; признак завершения программы (не 0)

SYM db "@" ; символ, выводимый на экран

ATRIBUT1 db 14 ; атрибут символа (жёлтый)

ATRIBUT2 db 10 ; атрибут символа (зелёный)

POS dw 3840 ; позиция начального вывода символа

OLD_CS dw ? ; адрес сегмента старого вектора 1Сh

OLD_IP dw ? ; адрес смещения старого вектора 1Сh

data ends

code segment

assume cs:code, ds:data

; Подпрограмма обработки прерывания 1Сh

NEW_1C proc far

push ax ; сохранить все регистры

push bx

push cx

push dx

push ds

push es

mov ax, DATA ; установить ds на сегмент данных

mov ds, ax ; основной программы

mov ax, 40h ; установить es на

mov es, ax ; сегмент данных bios

mov ax, es:[1ch]

mov bx, es:[1ah]

cmp bx , ax

jne m5

jmp back

m5: mov al, es:[bx]

mov es:[1ch], bx

cmp al, 30h

jnz m1

mov EXIT, 1

jmp back

m1: cmp al, 35h

jne m6

mov dl, ATRIBUT1

mov dh, ATRIBUT2

mov ATRIBUT1, dh

mov ATRIBUT2, dl

jmp back

m6: cmp al, 38h ; стрелка вверх

jz m2

cmp al, 32h ; стрелка вниз

jz m3

cmp al, 34h ; стрелка влево

jz m4

cmp al, 36h ; стрелка вправо

jnz back ; неиспользуемая клавиша

mov DIRECT, 3

jmp back

m2: mov DIRECT, 1

jmp back

m3: mov DIRECT, 4

jmp back

m4: mov DIRECT, 2

back: pop es

pop ds

pop dx

pop cx

pop bx

pop ax

iret

NEW_1C endp

; Подпрограмма очистки экрана

CLS proc near

push cx

push ax

push si

xor si, si

mov ah, 7

mov dl, ' '

mov cx, 2000

CL1: mov es:[si], ax

inc si

inc si

loop CL1

pop si

pop ax

pop cx

ret

CLS endp

; Подпрограмма задержки

DELAY proc near

push cx

mov cx, 100

d12: push cx

xor cx,cx

d11: nop

loop d11

pop cx

loop d12

pop cx

ret

DELAY endp

; Подпрограмма вывода символа с заданным атрибутом

OUT_SYMBOL proc near

push ax

push bx

mov al, SYM

mov ah, ATRIBUT1

mov bx, POS

call DELAY

mov es:[bx], ax

pop bx

pop ax

ret

OUT_SYMBOL endp

; Основная программа

START: mov ax, DATA

mov ds, ax

; чтение вектора прерывания

mov ah, 35h

mov al, 1Ch

int 21h

mov OLD_IP, bx

mov OLD_CS, es

; установка вектора прерывания

push ds

mov dx, offset NEW_1C

mov ax, seg NEW_1C

mov ds, ax

mov ah, 25h

mov al, 1Ch

int 21h

pop ds

mov ax, 0B800h

mov es, ax

call CLS

call DELAY

p1: cmp EXIT, 0

jne quit

cmp DIRECT, 1

jz p2

cmp DIRECT, 2

jz p3

cmp DIRECT, 3

jz p4

mov ax, POS

add ax,160

cmp ax, 3999

jg p1

mov POS, ax

call OUT_SYMBOL

jmp p1

p2: mov ax, POS

sub ax, 160

jl p1

mov POS, ax

call OUT_SYMBOL

jmp p1

p3: mov ax, POS

sub ax, 2

jl p1

mov POS, ax

call OUT_SYMBOL

jmp p1

p4: mov ax, POS

add ax, 2

jg p1

mov POS, ax

call OUT_SYMBOL

jmp p1

quit: call CLS

mov dx, OLD_IP

mov ax, OLD_CS

mov ds, ax

mov ah, 25h

mov al, 1Ch

int 21h

mov ax, 4c00h

int 21h

CODE ends

end START

Варианты заданий

Во всех вариантах задания завершение программы осуществляется при вводе цифры 0.

1. Выводить последовательно цифры от 0 до 9 в одно место экрана. При вводе с клавиатуры какой-либо цифры менять темп вывода. Значение задержки между выводом очередного символа определять следующим способом: введённую цифру умножить на 2⁹, это и будет число повторений цикла задержки. Для анализа нажатия клавиши использовать вектор 1Ch.

2. Выводить в одно место экрана поочерёдно код пробела и код какого-нибудь символа. Задержка между выводом каждого символа определяется нажатием цифровой клавиши следующим способом: введённую цифру умножить на 2⁹, это и будет число повторений цикла задержки. Для анализа нажатия клавиши использовать вектор 1Ch.

3. Выводить в одно место экрана введённый символ до тех пор пока не будет введён другой символ. Менять при выводе атрибут символа циклически от 1 до 15. Для анализа нажатия клавиши использовать вектор 1Ch.

4. Выводить в текущее положение курсора символ #. Следующий символ # выводить в позицию выше, ниже, левее или правее текущего символа, в зависимости от нажатия клавиш “8”, “2”, “4”, “6” на цифровой клавиатуре. Вывод осуществлять непрерывно с некоторой задержкой. Задержка между выводом каждого символа определяется нажатием цифровой клавиши, следующим способом: введённую цифру умножить на 2⁹, это и будет число повторений цикла задержки. Для анализа нажатия клавиши использовать вектор 1Ch.

5. Выводить в текущее положение курсора символ, введённый с клавиатуры. Этот же символ выводить в позицию выше, ниже, левее или правее текущего символа, в зависимости от нажатия клавиш “8”, “2”, “4”, “6” на цифровой клавиатуре. С клавиатуры можно ввести любую латинскую букву, при этом, выводимый символ изменяется на введённый символ. Вывод осуществлять непрерывно с некоторой задержкой. Задержка между выводом каждого символа определяется нажатием цифровой клавиши, следующим способом: введённую цифру умножить на 2⁹, это и будет число повторений цикла задержки. Для анализа нажатия клавиши использовать вектор 1Ch.

6. В программе имеются два циклических счётчика, считающих от 0 до 23 и от 0 до 79. Их значение определяет соответственно строку и столбец для вывода символа на экран. При нажатии какойлибо клавиши на экран выводится символ % в положение, определяемое состоянием счётчиков на момент вывода. Для анализа нажатия клавиши использовать вектор 1Ch.

7. В программе имеется циклический счётчик, считающий от 1 до 6. При нажатии любой клавиши содержимое счётчика преобразуется в ASCII код и выводится в определённое место экрана, после чего счётчик продолжает считать. Для анализа нажатия клавиши использовать вектор 1Ch.

8. Посчитать за какое время процессор выполнить 1 000 000 команд mov DI, SI; add DI, SI; mul SI. Для подсчёта времени использовать вектор 1Ch. Выводить на экран преобразованное в ASCII коды число тиков таймера, затраченное на операцию.

9. Очистить экран. Вывести несколько строк произвольного текста (атрибут 14). Перехватив прерывание печати экрана Print Screen (Int 5h), менять атрибуты всех строк экрана циклически от 1 до 15. Каждое нажатие клавиши Print Screen вызывает изменение атрибута.

10. Выводить ежесекундно в правом верхнем углу экрана системное время “часы:минуты:секунды”.

11. Вывести несколько строк произвольного текста, содержащие лишь латинские буквы. Каждые 10 секунд заглавные буквы сменяются строчными и т. д.

12. В программе имеется циклический счётчик, считающий от 00h до FFh. Его значение преобразуется в ASCII код и выводится в левом верхнем углу экрана через 18 тиков таймера. При нажатии клавиши ‘2’ время вывода уменьшается вдвое, а при повторном нажатии время вывода увеличивается в два раза. Для анализа нажатия клавиши и подсчёта числа тиков таймера использовать вектор 1Ch.

13. Заполнить экран произвольной информацией. Перехватить прерывание 1Ch, по нажатию клавиши ‘1’ осуществить горизонтальный скроллинг всего экрана влево на один столбец, при нажатии клавиши ‘2’ скроллинг вправо на один столбец.

14. Очистить экран. Вывести несколько строк произвольного текста. Перехватить прерывание экрана (Int 5h). Первый вызов этого прерывания располагает строки вертикально, следующий «нормально» и т.д.

15. Очистить экран. Заполнить его произвольной информацией. Перехватить прерывание экрана (Int 5h). Первый вызов этого прерывания переносит строчки верхней половины экрана на место нижних, а нижние на место верхних. Следующий вызов прерывания снова меняет их местами и т.д.

16. Выводить последовательно цифры от 0 до 9 в одно место экрана. При вводе с клавиатуры какой-либо цифры менять темп вывода. Значение задержки между выводом очередного символа определять следующим способом: введённую цифру умножить на 2⁹, это и будет число повторений цикла задержки. Для анализа нажатия клавиши использовать вектор 1Ch.

17. Выводить в одно место экрана поочерёдно код пробела и код какого-нибудь символа. Задержка между выводом каждого символа определяется нажатием цифровой клавиши следующим способом: введённую цифру умножить на 2⁹, это и будет число повторений цикла задержки. Для анализа нажатия клавиши использовать вектор 1Ch.

18. Выводить в одно место экрана введённый символ до тех пор пока не будет введён другой символ. Менять при выводе атрибут символа циклически от 1 до 15. Для анализа нажатия клавиши использовать вектор 1Ch.

19. Выводить в текущее положение курсора символ #. Следующий символ # выводить в позицию выше, ниже, левее или правее текущего символа, в зависимости от нажатия клавиш “8”, “2”, “4”, “6” на цифровой клавиатуре. Вывод осуществлять непрерывно с некоторой задержкой. Задержка между выводом каждого символа определяется нажатием цифровой клавиши, следующим способом: введённую цифру умножить на 2⁹, это и будет число повторений цикла задержки. Для анализа нажатия клавиши использовать вектор 1Ch.

20. Выводить в текущее положение курсора символ, введённый с клавиатуры. Этот же символ выводить в позицию выше, ниже, левее или правее текущего символа, в зависимости от нажатия клавиш “8”, “2”, “4”, “6” на цифровой клавиатуре. С клавиатуры можно ввести любую латинскую букву, при этом, выводимый символ изменяется на введённый символ. Вывод осуществлять непрерывно с некоторой задержкой. Задержка между выводом каждого символа определяется нажатием цифровой клавиши, следующим способом: введённую цифру умножить на 2⁹, это и будет число повторений цикла задержки. Для анализа нажатия клавиши использовать вектор 1Ch.

21. В программе имеются два циклических счётчика, считающих от 0 до 23 и от 0 до 79. Их значение определяет соответственно строку и столбец для вывода символа на экран. При нажатии какой-либо клавиши на экран выводится символ % в положение, определяемое состоянием счётчиков на момент вывода. Для анализа нажатия клавиши использовать вектор 1Ch.

22. В программе имеется циклический счётчик, считающий от 1 до 6. При нажатии любой клавиши содержимое счётчика преобразуется в ASCII код и выводится в определённое место экрана, после чего счётчик продолжает считать. Для анализа нажатия клавиши использовать вектор 1Ch.

23. Посчитать за какое время процессор выполнить 1 000 000 команд mov DI, SI; add DI, SI; mul SI. Для подсчёта времени использовать вектор 1Ch. Выводить на экран преобразованное в ASCII коды число тиков таймера, затраченное на операцию.

24. Очистить экран. Вывести несколько строк произвольного текста (атрибут 14). Перехватив прерывание печати экрана Print Screen (Int 5h), менять атрибуты всех строк экрана циклически от 1 до 15. Каждое нажатие клавиши Print Screen вызывает изменение атрибута.

25. Выводить ежесекундно в правом верхнем углу экрана системное время “часы:минуты:секунды” .

Вопросы по теме

В чём суть концепции прерывания?

Как работает система прерывания по вектору?

В чём отличие команд ret и iret?

Какие способы получения/изменения вектора прерывания Вы знаете?

Как вызвать программное прерывание?

Какие существуют способы передачи параметров в подпрограмму обработки прерываний и возврата параметров из неё?

Какие действия производит процессор при получения запроса на прерывание?

В чём отличие команд call и int?

Федеральное агентство РФ по образованию

Государственное образовательное учреждение

Высшего профессионального образования

Донской государственный технический университет

Кафедра "ПОВТ и АС"

Методы распределения загрузки многопроцессорных вычислительных систем

Методические указания к лабораторным работам

по дисциплине «Архитектура вычислительных систем»

Ростов-на-Дону

2003 г.

ВВЕДЕНИЕ

Задача распределения (планирования) загрузки вычислительной системы (ВС) возникают уже и том случае, когда имеется только один процессор. Типичным примером является планирование загрузки ЭВМ, работающей в режиме мультипрограммирования. Задача определения последовательности обработки процессов на ЭВМ известна в различных постановках и представляет собой серьезную самостоятельную проблему, называемую в исследовании операций задачей упорядочения. Содержанием задач упорядо­чения является выбор дисциплины обслуживания с таким расчетом, чтобы некоторый принятый критерий качества функционирования системы достигал экстремального значения.

При планировании загрузки для многопроцессорных и многомашинных систем, содержащих более одного процессора, задача существенно услож­няется. Оптимальные решения получены лишь для некоторых частных случаев, в общем же случае решение не получено. Практически планирование загрузки теперь уже не сводится лишь и задаче упорядочения. Наряду с этой задачей должна быть решена, причем в первую очередь, задача распределения загрузки процессоров, т.е. задача определения того, какие именно программные блоки из числа заданных должны обрабатываться на каждом из процессоров. Иначе говоря, требуется сопоставить каждой вершине граф-схеме алгоритма или программы (работе) некоторый процессор и определить последовательность реализации работ таким образом, чтобы либо минимизировать общее время решения данной задачи на ВС, либо по­лучить максимальную загрузку ВС и обеспечить заданную надежность. Существенной отличительной особенностью в данной задаче является то, что необходимо соблюдать требование очередности выполнения отдельных работ определяемой алгоритмом решения задачи.

Ниже рассматриваются некоторые методы анализа структур граф-схем программ и планирования загрузки многопроцессорных и многомашинных вы­числительных систем. На примерах иллюстрируется использование этих методов.

ЗАНЯТИЕ №1

Ярусно-параллельные формы представления граф-схем алгоритмов и определениеих характеристик

1. ЦЕЛЬ ЗАНЯТИЯ: практическое закрепление знаний о преобразовании схем алгоритмов к ЯПФ с целью их распараллеливания.

2. ОСНОВНЫЕ СВЕДЕНИЯ.

Отличительной особенностью многопроцессорных и многомашинных ВС является возможность параллельного выполнения независимых ветвей программы. Это свойство системы связано, с одной стороны, с наличием нескольких независимых вычислителей, а с другой - со свойствами самих алгоритмов, допускающих во многих случаях выделения параллельных ветвей.

Существует много различных способов отражения структуры вычислительного процесса, определяемого заданной программой для вычислительной системы. В частности, можно отметить различного рода блок-схемы, динамические диаграммы, граф-схемы и т.п. Для вычислительных систем, в которых могут быть организованы параллельные процессы, наиболее удобным оказывается использование граф-схем.

Всякую программу можно представить как некоторую последовательность работ (операторов), в результате чего получаем функциональный граф.

Для того чтобы связать функциональную граф-схему с реализацией ее в вычислительной системе, необходимо сопоставить каждой вершине функциональной граф-схемы некоторый вес, выражающий в условных единицах вре­мя выполнения данной работы с помощью вычислительных средств (процессора, ЭВМ) определенной производительности. Этот вес будем писать рядом с вершиной функциональной граф-схемы, которая теперь будет называется временной функциональной граф-схемой.

рис.1.1.

На рис.1.1. показан пример временной функциональной граф-схемы. Для отображения разветвлений в программах вводятся связи по управлению: сплошные дуги соответствуют функциональным связям между вершинами графа, а пунктирные - связям по управлению. Величины X_i, i=1,2,...,9 являются исходными данными, а величины Y_i, i=1,2,3 есть результаты, которые должны быть получены в процессе реализации программы.

Как показывают связи по управлению, в качестве результата работы ВС может получиться либо Y₁, либо Y₂, либо Y₃. Число типов процессоров равно двум.

Пусть имеется две работы, которые являются непосредственно функцио­нально связанными или связаны по управлению. Ту работу, в которой в качестве идентификатора операнда используется идентификатор результата другой работы, будем называть зависимой. Если некоторая работа G_j зависит от G_Y, то это означает,что при реализации программы работа G_Y должна быть выполнена раньше работы G_j.

Упорядочим, теперь вершины графа программы. Множеством первого яруса или просто первым ярусом называются те работы, которые не зависят ни от каких других работ. Множеством второго яруса или вторым ярусом на­зывают те работы, которые зависят, по крайней мере, от одной работы, входящей в первый ярус, и не зависят ни от какой другой работы. И вооб­ще, множеством f-го яруса или f-м ярусом называются те работы, которые зависят, по крайней мере, от одной работы (f-1)-го яруса и не зависят ни от одной работы, других ярусов с номерами, меньшими (f-1). Граф, соответствующий такому упорядочению работ, называется ярусно-параллельным графом, а относительно программы, сопоставляемой этому графу, говорят, что она представлена в ярусно-параллельной форме (ЯПФ).

На рис.1.2 показана ярусно-параллельная форма программы, представленной на рис.1.1. В дальнейшем формально будем рассматривать ЯПФ, содержащие только функциональные связи, так как это по существу не влияет на методику решения рассматриваемых ниже задач распределения загрузки.

рис.1.2

Для оценки структур ЯПФ вводятся специальные показатели. Эти пока­затели служат для классификации ЯПФ по их структурным особенностям, для оценки согласованности структуры решаемой задачи со структурой са­мой многопроцессорной вычислительной системы. С помощью показателей удобно сравнивать и оценивать структуры ЯПФ, соответствующие различным вариантам организации решения одной и той же задачи. Особый интерес представляет использование числовых характеристик на этапе исследования способности задачи к распараллеливанию и выбора алгоритма решения, ЯЛФ программы которого характеризуются наилучшими показателями.

Шириной f-го яруса в графе G ЯПФ программы называется число работ b^f, входящих в этот ярус.

Шириной B графа G ЯПФ называется максимальная ширина яруса в G.

Длиной (трудоемкостью) l^f_im i-ой работы в f-м ярусе ЯПФ относительно процессора (ЭВМ) m-го типа называется время ее реализации напроцессоре (ЭВМ) этого типа.

Длиной яруса l^f в графе G ЯПФ называется максимальная длина рабо­ты, входящей в этот ярус.

Длиной Ткр графа G ЯПФ называется величина наиболее длинного (крити­ческого) пути, ведущего к заключительному состоянию этого графа. Длина G определяет минимально-возможное время реализации данного графа.

Дебалансом яруса d^f называется разность между длиной яруса и длиной самой короткой работы, входящей в данный ярус.

Дебалансом графа d ЯЛФназывается сумма всех дебалансов ярусов данного графа.

Заполнением E^f яруса f в графе G называется сумма

где b^f - число работ в f-м ярусе; l^f_im - длина i-й работы находящейся в f-м ярусе для m-го процессора.