Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Метод списочных расписаний.

Читайте также:
  1. I. Определение и проблемы метода
  2. I. ОПРЕДЕЛЕНИЕ И ПРОБЛЕМЫ МЕТОДА
  3. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ
  4. I. Экспертные оценочные методы
  5. II МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ПОДГОТОВКЕ К ПРАКТИЧЕСКОМУ ЗАНЯТИЮ
  6. II. Категории и методы политологии.
  7. II. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ВЫПОЛНЕНИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Планирование для единичного ББ заключается в построении как можно более короткого плана. Поскольку эта проблема имеет переборный характер, внимание было сосредоточено на эвристических алгоритмах планирования. Среди таких алгоритмов наиболее подходящими оказались списочные расписания. Алгоритмы планирования по списку при линейном росте времени планирования при увеличении числа планируемых объектов, дают результаты, отличающиеся от оптимальных всего на 10-15%.

В таких расписаниях оператором присваиваются приоритеты по тем или

иным эвристическим правилам, после чего операторы упорядочиваются по

убыванию или возрастанию приоритета в виде линейного списка. В процессе

планирования затем осуществляется назначение операторов процессорам в по-

рядке их извлечения из списка.

На рисунке (а) представлена исходная ЯПФ. Номера вершин даны внутри

кружков, а время исполнения — около вершин. На рисунке (б) приведены уровни вершин. Под уровнем вершины понимается длина наибольшего пути из этой вершины в конечную. Построим для примера два расписания из множества возможных. Для каждого из них найдем характеристики всех вершин по соот

ветствущим алгоритмам и примем значения этих характеристик в качестве ве-

личин приоритетов этих вершин.

В первом расписании величина приоритета вершины есть ее уровень. Это

расписание УР. Во втором расписании величина приоритета вершины есть ее

уровень без учета времени исполнения, то есть здесь веса всех вершин полага-

ются одинаковыми (единичными).

 

УР УР без учета веса
П В П В
       
       
       
       
       
       
       
       
       
       
       
       

 

 

б) Приоритеты и списки вершин

(П— приоритеты, В — номера вершин)

в) Уровни вершин

 

                        номера вершины
                        уровни  

 

г) Реализация расписаний (Р1, Р2 — процессоры, X — простой процессора)

 

УР (по уровню вершин)

 

 

Р1                            
Р2 Х                         Х

 

УР без учета веса вершин

 

Р1               Х Х              
Р2 Х                         Х Х Х

 

Об оптимальности расписания можно судить по количеству простоев про-

цессоров. Первое расписание дает 2, второе — 5.

 

 


Дата добавления: 2015-07-08; просмотров: 220 | Нарушение авторских прав


Читайте в этой же книге: Введение | Большие задачи. | Методы повышения быстродействия | Формы параллелизма | Параллелизм независимых ветвей | Каждые 2 года количество транзисторов на кристалле удваивается | Основные этапы развития параллельной обработки | МЕЛКОЗЕРНИСТЫЙ ПАРАЛЛЕЛИЗМ | ЛЕКЦИЯ 8. | Независимостные архитектуры. |
<== предыдущая страница | следующая страница ==>
Алгоритм автоматического распараллеливания арифметических| Классификация Фишера для мелкозернистого паралеллизма

mybiblioteka.su - 2015-2024 год. (0.006 сек.)