Применение методов теории графов к организации вычислительного процесса

Размещение блоков программы в оперативной памяти компьютера: сведение к задаче коммивояжера. Пусть Применение методов теории графов к организации вычислительного процесса - №1 - открытая онлайн библиотека ‑ отдельные блоки программы, и пусть Применение методов теории графов к организации вычислительного процесса - №2 - открытая онлайн библиотека ‑ вероятность исполнения блока Применение методов теории графов к организации вычислительного процесса - №3 - открытая онлайн библиотека после Применение методов теории графов к организации вычислительного процесса - №4 - открытая онлайн библиотека . Если Применение методов теории графов к организации вычислительного процесса - №5 - открытая онлайн библиотека ‑ первый блок, а Применение методов теории графов к организации вычислительного процесса - №6 - открытая онлайн библиотека ‑ последний, то положим Применение методов теории графов к организации вычислительного процесса - №7 - открытая онлайн библиотека Если марковский процесс, описываемый матрицей переходов Применение методов теории графов к организации вычислительного процесса - №8 - открытая онлайн библиотека , является эргодическим, т. е. для него существует предельное распределение, которое не зависит от начального состояния процесса, то частоты исполнения отдельных блоков Применение методов теории графов к организации вычислительного процесса - №9 - открытая онлайн библиотека удовлетворяют матричному уравнению Применение методов теории графов к организации вычислительного процесса - №10 - открытая онлайн библиотека , нормализованному так, что сумма частот исполнения равна 1. Пусть величины Применение методов теории графов к организации вычислительного процесса - №11 - открытая онлайн библиотека найдены. Тогда, если Применение методов теории графов к организации вычислительного процесса - №12 - открытая онлайн библиотека ‑ время исполнения блока Применение методов теории графов к организации вычислительного процесса - №4 - открытая онлайн библиотека , то ожидаемое время исполнения всей программы равно Применение методов теории графов к организации вычислительного процесса - №14 - открытая онлайн библиотека . Если Применение методов теории графов к организации вычислительного процесса - №2 - открытая онлайн библиотека и Применение методов теории графов к организации вычислительного процесса - №11 - открытая онлайн библиотека известны, то можно рассмотреть задачу минимизации ожидаемого числа передач управления, производимых при выполнении программы. Если блок Применение методов теории графов к организации вычислительного процесса - №3 - открытая онлайн библиотека следует в памяти за блоком Применение методов теории графов к организации вычислительного процесса - №4 - открытая онлайн библиотека , то передача управления нужна всякий раз, когда после блока Применение методов теории графов к организации вычислительного процесса - №4 - открытая онлайн библиотека выполняется блок Применение методов теории графов к организации вычислительного процесса - №20 - открытая онлайн библиотека , отличный от Применение методов теории графов к организации вычислительного процесса - №3 - открытая онлайн библиотека . Ожидаемое число таких передач равно Применение методов теории графов к организации вычислительного процесса - №22 - открытая онлайн библиотека .

Пусть Применение методов теории графов к организации вычислительного процесса - №23 - открытая онлайн библиотека , если блок Применение методов теории графов к организации вычислительного процесса - №3 - открытая онлайн библиотека непосредственно следует за блоком Применение методов теории графов к организации вычислительного процесса - №4 - открытая онлайн библиотека в памяти, и Применение методов теории графов к организации вычислительного процесса - №26 - открытая онлайн библиотека в противном случае.

Пусть Применение методов теории графов к организации вычислительного процесса - №27 - открытая онлайн библиотека ‑ блок, состоящий из кодов начальных данных и кодов, которые не выполняются в виде команд. Тогда для всех Применение методов теории графов к организации вычислительного процесса - №28 - открытая онлайн библиотека имеем Применение методов теории графов к организации вычислительного процесса - №29 - открытая онлайн библиотека . Полагаем Применение методов теории графов к организации вычислительного процесса - №30 - открытая онлайн библиотека , если Применение методов теории графов к организации вычислительного процесса - №4 - открытая онлайн библиотека ‑ погледний блок в памяти, и Применение методов теории графов к организации вычислительного процесса - №32 - открытая онлайн библиотека , если Применение методов теории графов к организации вычислительного процесса - №4 - открытая онлайн библиотека - первый блок в памяти, в остальных случаях полагаем Применение методов теории графов к организации вычислительного процесса - №34 - открытая онлайн библиотека , Тогда рассматриваемая задача сводится к минимизации ожидаемого числа выполнения передач управления Применение методов теории графов к организации вычислительного процесса - №35 - открытая онлайн библиотека при условии, что Применение методов теории графов к организации вычислительного процесса - №36 - открытая онлайн библиотека есть матрица циклической перестановки, а это и есть задача коммивояжера (см. раздел 6.2.3).

Рассмотрим ситуацию, когда на входе компьютера ямеется некоторое множество задач, имеющих общие страницы в памяти. Требуется определить такую последовательность решения этих задач, чтобы минимизировать пересылки страниц памяти. Для решения построим граф, вершинам которого будут соответствовать задачи, а две вершины соединены ребром тогда и только тогда, когда они соответствуют задачам, имеющим общие страницы памяти. Каждому ребру сопоставляется вес, зависящий от числа общих страниц.

Тогда проблема активизации задач сводится к отысканию оптимального каркаса графа активизации. Особенность этой проблемы состоит в том, что чаще всего стоимость каркаса ‑ нелинейная функция от весов ребер.