Ценовая модель
Нашей целью является построение разбиения программы на нити, максимально использующего возникающие события локальности. Чтобы иметь возможность судить о степени оптимальности того или иного разбиения, необходимо ввести некоторую ценовую модель. Так как мы оптимизируем время выполнения программы, то естественно ввести веса узлов графа зависимости по данным, равные времени выполнения узла в последовательной программе.
Время выполнения узла может быть найдено с помощью профилирования программы. Для этого необходимо инструментировать исходный код программы, вставляя вызовы функций из библиотеки поддержки, вычисляющих время выполнения инструкций, и выполнить программу на нескольких наборах типичных входных данных. Для получения более точных результатов можно воспользоваться высокоточными аппаратными счетчиками, имеющимися на большинстве современных архитектур (например, инструкцией RDTSC для Pentium III и выше). Эта оценка времени выполнения точно показывает реальное время выполнения программы, но затрудняет эмуляцию кэша на этапе разделения на нити, так как сложно определить, насколько уменьшится время выполнения узла при попадании в кэш (возможно, при профилировании это попадание уже произошло).
Ценовая модель должна также отражать события локальности, происходящие во время выполнения программы. Статических весов для узлов DDG для этой цели недостаточно. Необходима эмуляция кэша в процессе разделения на нити и соответствующая корректировка времени выполнения узла.
