SSCC-PIPL: библиотека обработки изображений на многопроцессорных ЭВМ

Русин Е.В.

Содержание:

1. Основопологающие принципы

Мировой опыт создания библиотек параллельной обработки изображений для многопроцессорных систем традиционной архитектуры говорит о том, что:

Исходя из этого, нами сформулированы следующие принципы, которым должна подчиняться библиотека SSCC-PIPL:

2. Интерфейс библиотеки SSCC-PIPL

Интерфейс библиотеки SSCC-PIPL составляют следующие классы:

3. Распараллеливание алгоритмов

Пользователь имеет возможность выбрать один из следующих способов представления изображения на наборе исполняющих процессоров для наиболее эффективного распараллеливания вычислительного алгоритма:


4. Ввод-вывод

Библиотека SSCC-PIPL обеспечивает чтение-сохранение изображений в различных графических форматах за счет использования библиотеки CxImage, созданной Д. Пиццолато (Италия). CxImage - ANSI-совместимая библиотека и может использоваться в средах Unix, Windows, MacOS. Она доступна в исходном коде и не требует дополнительного лицензирования. Однако CxImage - последовательная библиотека, которая не поддерживает "распределенность" изображения по разным машинам. Поэтому в SSCC-PIPL операции ввода-вывода используют звездообразную топологию: один из исполняющих процессоров назначается корневым (или просто "корнем"), и именно он выполняет непосредственно дисковый ввод-вывод. Чтение изображения из файла выполняется по схеме "чтение файла корнем (посредством CxImage) - рассылка остальным исполняющим процессорам необходимых им данных от корня", а запись изображения в файл - по схеме "сбор данных на корне от исполняющих процессоров - запись изображения в файл корнем (посредством CxImage)".

5. Обработка ошибок

Специфика библиотеки SSCC-PIPL как инструмента для научных расчетов, ориентированного на максимальную эффективность, а также выбранная модель SPMD накладывают жесткие ограничения на стратегию обработки ошибок в программах, использующих библиотеку. Ветвление типа "если в результате выполнения функции F произошла ошибка, выполнить A, иначе B" в SPMD-программе приводит к необходимости синхронизации при завершении выполнения F - функция должна возвращать одинаковое значение на всех процессорах, характеризующее статус выполнения функции в целом. Множество всех возможных ошибочных ситуаций при выполнении подпрограмм библиотеки SSCC-PIPL можно разделить на четыре категории:

6. Параметризация операций алгоритмами

Преобразования изображения реализованы в библиотеке SSCC-PIPL как обобщенные операции. Для применения к изображению конкретного преобразования соответствующую обобщенную операцию необходимо параметризовать конкретным алгоритмом. При этом возник выбор между двумя возможными в C++ механизмами параметризации:

По соображениям производительности и универсальности SSCC-PIPL использует второй вариант - это позволило перенести накладные расходы, связанные с повышением уровня абстракции модели вычислений, на время компиляции программы пользователя, а не на время ее выполнения. Кроме того, такой подход позволяет выполнить так называемое "встраивание" функции вычисления значения пикселя - замену в двоичном коде вызова функции для каждого обрабатываемого пикселя телом этой функции - сильно затрудненное в случае механизма виртуальных функций. Как результат сделанного выбора, библиотека должна распространяться в исходном коде, компиляция программы пользователя выполняется дольше, но ее быстродействие значительно повышается.

7. Производительность

В результате тестовых расчетов получены ответы на два главных вопроса, необходимые для обоснования правильности выбранных методов реализации библиотеки.

Первый вопрос:  не слишком ли большие накладные расходы связаны с повышением уровня абстракции модели вычислений? Для ответа на этот вопрос на языке C++ было написано две программы медианной фильтрации изображения:

Второй вопрос:  какова эффективность распараллеливания вычислений, обеспечиваемого библиотекой?

Тестовые расчеты, выполненные на многопроцессорной ЭВМ МВС-1000/М ССКЦ, показали, что эффективность распараллеливания алгоритма медианной фильтрации с окнами осреднения от 3х3 до 21х21 пиксель на 8 процессорах составляет 95%.

8. Приложение (пример использования библиотеки в С++ программе)

Ниже приводится пример кода, реализующего алгоритм медианной фильтрации, написанного с помощью библиотеки SSCC-PIPL.

#include "ParImProLib.h" // заголовочный файл SSCC-PIPL
// заголовочные файлы стандартной билиотеки C++
#include
#include
#include
const char* g_szInputFileName = "Image_1.pcx"; // имя входного файла
const unsigned g_uiMedianFilterinWindowSize = 1; // радиус окрестности осреднения
using namespace ParImProLib; // пространство имен SSCC-PIPL
using namespace std;// класс-функтор, обеспечивающий выполнение медианной фильтрации
template
class CMedianFiltering {
public:
CMedianFiltering(
unsigned uiNeighborhood = 1 // радиус окресности осреднения
)
: m_uiNeighborhood(uiNeighborhood),
m_pixelsInNeighborhood((m_uiNeighborhood * 2 + 1) * (m_uiNeighborhood * 2 + 1)),
vecNeighborhood(m_pixelsInNeighborhood)
{
};
// оператор "скобки" - здесь выполняется фильтрация в отдельном пикселе
template typename
inline pixelType operator() (
const CNeighborhoodManipulator& neighborhood // манипулятор окресности, позволяющий получать значения соседних с текущим пикселей
) {
// алгоритм медианной фильтрации:
//
// значение пикселя в результирующем изображении
// =
// медиана (значение среднего пиксела после упорядочивания по возрастанию)
// окрестности этого пикселя на исходном изображении
unsigned uiNeighborhoodVectorIndex = 0;
for (int iNeighborhoodY = - static_cast(m_uiNeighborhood);
iNeighborhoodY <= static_cast(m_uiNeighborhood);
iNeighborhoodY++ ) {
for (int iNeighborhoodX = - static_cast(m_uiNeighborhood);
iNeighborhoodX <= static_cast(m_uiNeighborhood);
iNeighborhoodX++ ) {
// метод PixelRelativeToCurrent возращает значение пиксела, находящегося на заданном смещении от текущего
pixelType pixValue = neighborhood.PixelRelativeToCurrent(iNeighborhoodY, iNeighborhoodX);
vecNeighborhood[uiNeighborhoodVectorIndex] = pixValue;
uiNeighborhoodVectorIndex++;
}
}
// стандартный алгоритм nth_element помещает в середину вектора его медиану
nth_element(vecNeighborhood.begin(), vecNeighborhood.begin() + (m_pixelsInNeighborhood / 2), vecNeighborhood.end(), less());
return vecNeighborhood[m_pixelsInNeighborhood / 2];
};
/* Следующие четыре метода необходимы классу функтора для того, чтобы система могла корректно учесть краевые эффекты:
1. Избежать вычислений в граничных пикселах (для них недостаточно информации)
2. При необходимости подкачать значения пикселей вдоль границ разреза изображения на полосы с соседних процессоров
*/
// левая граница ядра фильтра
unsigned LeftMargin() const {
return m_uiNeighborhood;
};
// правая граница ядра фильтра
unsigned RightMargin() const {
return m_uiNeighborhood;
};
// верхняя граница ядра фильтра
unsigned TopMargin() const {
return m_uiNeighborhood;
};
// нижняя граница ядра фильтра
unsigned BottomMargin() const {
return m_uiNeighborhood;
};
private:
unsigned m_uiNeighborhood; // радиус окрестности осреднения
unsigned m_pixelsInNeighborhood; // общее число пикселей в окрестности осреднения
typedef vector CPixelVector;
CPixelVector vecNeighborhood; // вектор значений пикселей окрестности осреднения текущего пикселя
};
void main(int argc, char* argv[]) {
// Инициализация библиотеки
CRunTime::Instance().Start(&argc, &argv);
string strErrorDescription;
CImage image;
CImage::TPartitioningInfo pi(
CImage::PT_CutWithOverlap, // разрезать изображение на полосы с перекрытием соседних полос
1 // ширина перекрытия = 1 пиксел
);
// Прочитать входное изображение из файла
if (!image.Create(g_szInputFileName, pi, &strErrorDescription)) { // Только методы ввода-вывода возвращают свой статус.
// вывести сообщение об ошибке
CRunTime::Instance().Print(CRunTime::ms_uiPrintAll, "\nCannot create image: %s", strErrorDescription.c_str());
return;
}
CMedianFiltering filter(g_uiMedianFilterinWindowSize);
CRunTime::Instance().Print(
CRunTime::Instance().RootRank(),
"\n\nMedian filtering with window [%u x %u]...",
(uiMedianFilterinWindowSize * 2) + 1, (uiMedianFilterinWindowSize * 2) + 1
);
CRunTime::Instance().StartTimeMeasuring(); // Начать измерение времени
// Выполнить преобразование;
// Ко всем пикселам изображения будет применен оператор operator() объекта filter.
image.DoNeighborhoodToPixelOperation(filter);
CRunTime::Instance().ReportTimeElapsed(); // Завершить измерение времени и выдать сообщение о прошедшем интервале
// Сформировать имя выходного файла
ostringstream streamDestFileName;
streamDestFileName << "_Median_" << g_uiMedianFilterinWindowSize;
string strDestFileName(g_szInputFileName);
strDestFileName.insert(strDestFileName.find_last_of(L'.'), streamDestFileName.str());
// Записать результат преобразования в файл
if (!image.Save(strDestFileName, 16, &strErrorDescription)) {
CRunTime::Instance().Print(CRunTime::ms_uiPrintAll, "\nCannot save image: %s", strErrorDescription.c_str());
}
}