Средства разработки приложений
Еще раз подчеркнем, что иерархичность
Еще раз подчеркнем, что иерархичность графа обеспечивает то, что он является ациклическим.
Таким образом, к моменту обработки некоторого узла все узлы, от которых он зависит по данным, уже распределены на нити. Если какие-либо из таких узлов находятся в других нитях, то перед выполнением текущего узла необходимо провести синхронизацию со всеми такими нитями. Для того, чтобы осуществить такую синхронизацию, нужно завести по одной общей переменной для каждой нити. Присваивание значения i такой переменной для некоторой нити j означает, что эта нить выполнила узел i. Нить, ждущая результатов вычисления узла i, должна ждать, пока соответствующая общая переменная не примет нужного значения. Пример такой синхронизации показан на Рис. 2.
Времена выполнения каждой из нитей, проводящих синхронизацию, должны быть увеличены соответствующим образом. Нить, пишущая в общую переменную о результатах выполнения узла, дополнительно работает время t1. Нить, ждущая данных от нескольких узлов, ожидает последний из выполняющихся узлов, после чего тратит время t2. Эти времена являются параметрами алгоритма.
Рис. 2. Пример синзронизации
2.1.3.2. Учет возникающих событий локальности Для учета событий локальности для каждой нити необходимо эмулировать кэш процессора, на котором она выполняется. При распределении текущего узла на какую-либо нить необходимо проверить все переменные, которые читаются либо пишутся узлом, на попадание в кэш. Если попадание произошло, то время выполнения узла должно быть уменьшено на интервал времени t3, также являющийся параметром алгоритма.
Рис. 3. Пример эмулирования кэша
Для учета событий как временной, так и пространственной локальности необходимо моделирование линий кэша, т.е. помещение в кэш не одной переменной, а некоторого блока памяти, окружающего нужную переменную. Моделирование различных типов кэшей приведет к разным результатам при разделении на нити.
Пример моделирования событий локальности изображен на Рис. 3.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий