В терминах теории графов приведите постановку задачи оптимального отображения параллельных процессов на архитектуру многопроцессорной вычислительной системы.
 Ответ 
Пусть - граф информационных связей процессов, где - вершины графа, отождествляемые с процессами, - ребра графа, отождествляемые с информационными связями между процессами: - процессы связаны информационно (точнее – процесс передает информацию процессу ). Обозначим вычислительные сложности процессов , соответственно; - количество информации в байтах, которое процесс передает процессу .
Положим, что имеется многопроцессорная вычислительная система с универсальными процессорами, каждый из которых может выполнить любой из процессов . Пусть - граф (возможно, циклический) данной МВС. Здесь - вершины графа, соответствующие процессорам, - ребра графа, отождествляемые с коммуникационной сетью: =1 означает, что имеется возможность прямой передачи данных от процессора процессору ; =0 - такой возможности нет. Производительности процессоров обозначим ,,...,, соответственно. Связь будем описывать двумя величинами:
- - латентность канала связи - время, необходимое для организации передачи данных от процессора процессору ;
- - величина, обратная пропускной способности канала связи - время, необходимое для передачи байта данных от процессора процессору (без учета времени ).
Задачей оптимального отображения параллельных процессов на процессоры называется задача оптимального отображения графа на граф - задача поиска такого распределения процессов по процессорам , которое минимизирует некоторый критерий оптимальности (обычно время вычислений).
Введем в рассмотрение (*) отображающую матрицу={, [1,], [1,]}, компоненты которой имеют следующий смысл: - процесс назначен на выполнение процессору ; - процесс не назначен на выполнение процессору .
Во введенных обозначениях задачу оптимального отображения графа на граф можно формализовать следующим образом: найти отображающую матрицу такую, что (). Здесь критерий оптимальности, {} - множество допустимых отображений, - оптимальная отображающая матрица.