ВведениеКроме циклов по всем ячейкам сетки, в программе может встретиться необходимость организовать другие типы циклов: как по другим элементами сетки (например, в двумерном случае — по вершинам и ребрам), так и по определенным ячейкам (например, по границе области).Вершины и ребраПредположим, что как предлагается в разделе Способы адресации массивов, для хранения информации о сетке используется массив Grid. По этой информации можно построить массивы для описания других элементов сетки и значений на этих элементах.ГраницыОсобенными элементами сетки, требующими отдельной обработки являются, в частности, ячейки, расположенные на границе. Для обхода таких ячеек необходимо различать ячейки на границе и остальные ячейки. Наиболее простым способом это сделать будет добавление одного поля в элементы массива Grid, которое будет хранить информацию, является ли данная ячейка внутренней или граничной. В выше приведенных примерах для этого использовалось поле is_inner.В результате, цикл по границе можно записать следующим образом:
for (n = 0; n < N; n++) { Для решения этой проблемы можно использовать массив Border (длиной B), в котором хранятся номера граничных ячеек. Тогда цикл будет записан следующим образом:
for (b = 0; b < B; b++) { БиблиотекаОписанные примеры показывают, что в библиотеку можно вынести всю работу с сеткой: представление сетки, представление свойств отдельных элементов сетки, заведение массивов по элементам сетки, представление информации для удобного описания циклов по элементам сетки.В результате, разработка программы будет выглядеть следующим образом.
Пользователь с помощью внешних систем строит необходимую сетку, которая записывается в одном из общепринятых форматов хранения сетки.
При инициализации библиотеки пользователь передает информацию о сетке (и, возможно, дополнительную информацию) в библиотеку.
Библиотека предоставляет пользователю массивы, описывающие информацию об элементах сетки: в двумерном случае — о ячейках, о ребрах, о вершинах, их свойства (например, является ли элемент граничным) и тому подобное.
Библиотека так же предоставляет пользователю возможность заводить массивы данных по элементам сетки.
Пользователь, желательно стандартным образом, описывает циклы по элементам сетки. Внутри циклов пользователь описывает необходимые вычисления.
Необходимо, чтобы эти витки циклов были независимы, запрограммированы в стиле функциональной функции map, т.е. использовали номер витка цикла только для обращения к элементу массивов с данным номером. Для обращения к соседним (в смысле сетки) элементам сетки необходимо использовать структуры описания сетки, предоставляемые библиотекой, и использовать индексы, описанные в данных структурах.
Как будет отдельно показано, такие ограничения позволят эффективно распараллеливать программу. Отметим, что на основе данных ограничений возможна разработка специализированного языка программирования, в котором существуют специальные конструкции по элементам сетки, в которых указанные ограничения проверялись бы на этапе компиляции программы.
ЗаключениеМы привели рекомендации по преобразованию кода программы, которые приводят к разделению его на универсальную (библиотечную) и специфичную части. В универсальной части сосредоточена работа с сеткой, заведение массивов данных (по элементам сетки). В специфичной части сосредоточены вычисления над данными. Такое разделение позволяет один раз описать универсальную часть, а затем ее многократно использовать.Вынесение операций над сеткой в библиотеку вынуждает пользователя-программиста описывать циклы, обходящие элементы сетки, единым рекомендованным образом. Использование такого ограниченного способа описания позволяет применить способ распараллеливания методом «Преобразования массивов», описанный в разделе Способы распараллеливания циклов. |