Последний раз редактировалось Circiter 08.10.2011, 13:58, всего редактировалось 5 раз(а).
При попытке написать код на C и протестировать этот изотрейсер, наткнулся таки на проблемы с распараллеливанием. Как и ожидалось, этап выделения элементарных отрезков параллелится на ура, ведь все ячейки абсолютно независимы. Полученные отрезки сразу же можно рисовать.
Но ведь нам-то нужно протрассировать каждую изолинию и результирующую векторную картинку представить списком оных. Возникает проблема синхронизации, которая необходима, чтобы ячейки, принадлежащие одной и той же изолинии "осознали" свое единство. Следующая пара абзацев демонстрирует мою идею решения этой проблемы, но написаны они несколько абстрактно и своей расточительностью ресурсов могут повредить здоровью всякого, кто занимался практической реализацией серьезных параллельных алгоритмов. :)
А идея-то проста. Мне кажется, что ячейки можно упорядочить так, чтобы среди двух ячеек меньшей считалась ячейка, являющаяся одновременно самой левой и самой верхней; пока не знаю как такой критерий записать, но суть заключается в предположении о существовании наименьшей (i.e. минимальной по такому порядку и единственной) ячейки.
Допустим, для определенности, что у нас только одна замкнутая изолиния. Также предположим, что каждая ячейка обрабатывается в отдельном потоке. С пустыми ячейками понятно -- их потоки сразу же завершаются. В каждой же ячейке интереса после определения направления элементарного отрезка её поток вычисляет номер ячейки в смысле намеченного выше упорядочивания и посылает сообщение с этим номером потоку следующей ячейки контура в порядке его обхода, ну скажем, по часовой стрелке.
Такое сообщение поток может получить и от предыдущей ячейки и если присланный при этом номер будет больше его собственного, то такой поток сразу же создаст новый элемент в списке контуров (в соотвествии с гипотезой о единственности самого левого верхнего элемента) и запишет в этот элемент ссылку на свою ячейку. В любом случае все потоки ячеек интереса перед завершением своей работы записывают данные своей ячейки в глобальный пул ячеек, сохраняя код ориентации элементарного отрезка.
Воть. Фактически мы параллельно (правда с пересылкой сообщений) генерируем список ведущих ячеек каждой изолии. Когда нам нужно получить конкретную изолинию, например чтобы её нарисовать, нам придется пройти по соответсвующий ссылке, нарисовать соответствующий элементарный отрезок, пройти по следущей ссылке, нарисовать второй отрезок, etc. То есть можно считать, что изолинии уже хранятся в виде связных списков, полченных чисто параллельно. Но для испольщования этих связных списков их ве-равно придется обходить в последовательном режиме.
Что вы думаете об этой (концептуальной) схеме?
|
