SSCC-PIPL: Image Processing Library on Multiprocessor Computers

RUSIN E.V.

Content:

1. Basic Principles

World experience of parallel image processing libraries creation for multiprocessor computers of traditional architecture indicates that:

Based upon this, we formulate the following principles for SSCC-PIPL library building:

2. SSCC-PIPL Library Interface

The following classes constitute SSCC-PIPL library interface:

3. Algorithm Parallelization

User may choose one of the following ways to distribute an image among executing processors to obtain most effective parallelization of computational algorithm:


4. IO Operations

SSCC-PIPL library provides reading and writing images in various graphic formats by using CxImage library by Davido Pizzolatto, Italy. CxImage is ANSI-compatible and can be used in UNIX, Windows and MacOS environments. It is freely distributed in source code and does not require additional licensing. However, CxImage is sequential library and does not support 'distributedness' of an image among several computers. That's why SSCC-PIPL executes IO operations using star-like topology: one of executing processors is designated as root and performs disk IO operations. So, reading image from file is performed by the scheme "the root reads file with CxImage and sends other processors necessary data", and writing image to file is performed by the scheme "root gathers whole image data from other processors and writes to file with CxImage".

5.Error Handling

Specific character of SSCC-PIPL library as of a scientific calculations tool oriented to maximal performance, as well as the SPMD model chosen place hard restrictions on the error handling strategy in the programs using the library. Branching like "if the function F returned error, execute A; otherwise, B " in SPMD program causes the necessity of synchronization in the places of code where F returns its execution status, since F must return same value (status of the execution 'as a whole') on all the processors. The set of possible erroneous situations that can occur during SSCC-PIPL subprograms execution can be divided into four groups:

6. Parametrization of Operations by Algorithms

Image transformation implemented in SSCC-PIPL as generic operations. To apply concrete transformation to an image, one should parametrize the corresponding generic operation by concrete algorithm. At the implementation stage, the choice appeared between two C++ parametrization mechanisms:

From considerations of performance and universality, SSCC-PIPL uses the second approach; it allowed carrying overheads due to computation model abstraction level increase from program execution time to compile time. Besides, such an approach allows so-called embedding of the function that calculates pixel value, i.e. inserting a copy of the function body into each place the function is called. Embedding is not available for virtual functions. As a result of this choice, the library must be distributed in source code, user's program compiles longer, but executes faster.

7. Performance

Answers on two main questions that are necessary to justify chosen approaches were obtained as a result of test calculations.

The first question:  нIs overhead due to computation model abstraction level increasing reasonable? To answer the question, two C++ image median filtering programs were written:

Pixel values calculation itself is implemented similarly in both programs, the programs differs only by the pixel access mechanism. The test showed that the abstraction level increasing overhead does not exceed 10% from calculations performance. At the same time program implementation and debug becomes much simpler.

The second question:  What parallelization efficiency does the library provides? Tests executed on the multiprocessor computer MVS-1000/M of Siberian Supercomputer Center showed that parallelization efficiency of median filtering with window sizes from 3 by 3 to 21 by 21 pixels on 8 processors is 95%.

8. Appendix (sample C++ program code using the library)

НBelow is the sample median filtering code written with SSCC-PIPL library.

#include "ParImProLib.h" // SSCC-PIPL header
// заголовочные файлы стандартной билиотеки C++
#include
#include
#include
const char* g_szInputFileName = "Image_1.pcx"; // input file path
const unsigned g_uiMedianFilterinWindowSize = 1; //filtering window size
using namespace ParImProLib; // SSCC-PIPL namespace
using namespace std;// functor class, implementing median filtering algorithm
template
class CMedianFiltering {
public:
CMedianFiltering(
unsigned uiNeighborhood = 1 // filtering window size
)
: m_uiNeighborhood(uiNeighborhood),
m_pixelsInNeighborhood((m_uiNeighborhood * 2 + 1) * (m_uiNeighborhood * 2 + 1)),
vecNeighborhood(m_pixelsInNeighborhood)
{
};
// Function call operator; implements filtering in one pixel
template typename
inline pixelType operator() (
const CNeighborhoodManipulator& neighborhood // neighborhood manipulator, providing access to pixels close to the current
) {
// median filtering algorithm:
//
// result image pixel value
// =
// median (the value in the middle after the sort in ascending order)
// of the original image pixel 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 method returns the value of the pixel shifted by given vector from the current one
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];
};
/*The following four methods are necessary to allow the system to account side effects:
1. Avoid calculations in margin pixels (there is not enough information for them)
2.Take, if necessary, the pixel values along the margin between strips from the neighbor processors
*/
// the left filter margin
unsigned LeftMargin() const {
return m_uiNeighborhood;
};
// the right filter margin
unsigned RightMargin() const {
return m_uiNeighborhood;
};
// the top filter margin
unsigned TopMargin() const {
return m_uiNeighborhood;
};
// the bottom filter margin
unsigned BottomMargin() const {
return m_uiNeighborhood;
};
private:
unsigned m_uiNeighborhood; //filtering radius
unsigned m_pixelsInNeighborhood; // total pixel count in the filtering window
typedef vector CPixelVector;
CPixelVector vecNeighborhood; // values of the pixels from the filtering window of the current pixel
};
void main(int argc, char* argv[]) {
// library initialization
CRunTime::Instance().Start(&argc, &argv);
string strErrorDescription;
CImage image;
CImage::TPartitioningInfo pi(
CImage::PT_CutWithOverlap, // cut image with neighbor strips overlapping
1 // ширина перекрытия = 1 пиксел
);
// Read input image from the file
if (!image.Create(g_szInputFileName, pi, &strErrorDescription)) { // Only IO methods return completion status..
// Show error message
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(); // initiate time measuring
// Выполнить преобразование;
// Perform transformation; filter.operator() will be applied to all the pixels of image object.
image.DoNeighborhoodToPixelOperation(filter);
CRunTime::Instance().ReportTimeElapsed(); //finish time measuring and show time elapsed report
// Construct output file name
ostringstream streamDestFileName;
streamDestFileName << "_Median_" << g_uiMedianFilterinWindowSize;
string strDestFileName(g_szInputFileName);
strDestFileName.insert(strDestFileName.find_last_of(L'.'), streamDestFileName.str());
//Write the result image in the file
if (!image.Save(strDestFileName, 16, &strErrorDescription)) {
CRunTime::Instance().Print(CRunTime::ms_uiPrintAll, "\nCannot save image: %s", strErrorDescription.c_str());
}
}