Информационные графы с векторными весами вершин
Часто в состав ВС включают средства (процессоры) разной специализации и производительности. Например, МВК может комплексироваться разными ЭВМ, но допустимо исследование его как единой ВС. Новые ВС могут дополняться процессорами — эмуляторами ранее распространенных ЭВМ — для использования ранее разработанных программных продуктов. ВС, используемые в системах управления, дополняются процессорами, специализированных для решения конкретных задач, и т.д.
Появляется дополнительный выбор: на процессор какого типа возложить решение задачи? На основе каких типов процессоров с учетом количества процессоров разного типа целесообразно скомпоновать систему? Как спланировать работу неоднородной ВС таким образом, чтобы данный алгоритм выполнялся за минимальное время?
Пусть ВС комплектуется процессорами k типов по производительности и специализации. Пусть ni , i = 1 ... k, — число процессоров i-го типа. Тогда для каждой работы следует задавать не скалярный вес (такими весами мы пользовались ранее), а вектор — вес. Каждая компонента такого веса равна времени выполнения работы процессорами соответствующего типа. Например, для k = 2 граф G с векторными весами вершин представлен на рис. 10.15а, а расширенная матрица следования — на рис. 10.15б.
Рис. 10.15. К распределению работ в неоднородной ВС: а — информационный граф, б — расширенная матрица следования
На таком графе можно сформулировать оптимизационные задачи 1 и 2 (см. лекцию 20). Однако их методы решения весьма трудоемки (задачи экспоненциальной сложности), поэтому их заменяют эвристическими методами (полиномиальной сложности). Более того, пусть мы умеем решать задачу нахождения плана выполнения работ, минимизирующего время выполнения всего алгоритма (т.е. задачу 2). Тогда на основе этого решения можно давать заключение о возможности применения ВС в каждой конкретной комплектации, т.е. о решении задачи 1. При этом придется испытывать различные комбинации такой комплектации.
Таким образом, необходимо построить достаточно эффективный алгоритм диспетчирования неоднородной ВС, т.е. эвристический алгоритм планирования выполнения за минимальное время алгоритма, заданного информационным графом с векторными весами вершин.
