Mandelbrot - Code Sample

void parallel_mandelbrot::solve_area(int x0, int y0, int x1, int y1, int maximum_iterations)
{
    /*This function is not used for the parallel, but is required due to the class design given by Ian D. Romanick.*/
    assert(false);
}

unsigned int __stdcall parallel_mandelbrot::Worker(VOID* This)
{
    /*
    Enter the real worker method.
    By having this simple wrapper method, this is implict instead of explict.
    */
    return reinterpret_cast<parallel_mandelbrot*>(This)->worker();
}

unsigned int parallel_mandelbrot::worker(void)
{
    bool counted = true;
    
    do
    {
        /*Get next data.*/
        EnterCriticalSection(&CS_queueAccess);
        while (work.empty())    /*Wait for data if needed*/
            /*We will pause for 50 ms to wait for data. If we are woken
            due to data being added, continue, else freeze us and possibly
            shut down this thread.*/
            if (!CV_queueNotEmpty.Wait(&CS_queueAccess, 50))
            {
                if (counted)
                {
                    activeThreads--;
                    printf("Worker Thread Frozen....%i active\n", activeThreads);
                    counted = false;
                }
                if (activeThreads == 0) /*All work is done, exit.*/
                {
                    LeaveCriticalSection(&CS_queueAccess);
                    printf("Worker Thread Complete\n");
                    return 0;
                }
            }
            /*If we've been frozen, make sure to unfreeze us.*/
            else if (!counted)
            {
                activeThreads++;
                printf("Worker Thread Thawed....%i active\n", activeThreads);
                counted = true;
            }
        std::queue<workdata>::reference t = work.front();
        const int x0 = t.x0;
        const int y0 = t.y0;
        const int x1 = t.x1;
        const int y1 = t.y1;
        const int maximum_iterations = t.maximum_iterations;
        work.pop();
        LeaveCriticalSection(&CS_queueAccess);

        /* The area will eventually be subdivided.  Be smart about the
         * subdivision.  If the divided width would be too small, don't divide on
         * X.  Ditto for the height.
         */
        const int delta_x = (x1 - x0);
        const int delta_y = (y1 - y0);
        const bool divide_width = delta_x > 16;
        const bool divide_height = delta_y > 16;
        
        /* Calculate the iteration counts around the border of the area.
         */
        const int same[4] = {
            solve_row(x0, x1, y0, maximum_iterations),
            solve_row(x0, x1, y1, maximum_iterations),
            solve_col(x0, y0, y1, maximum_iterations),
            solve_col(x1, y0, y1, maximum_iterations)
        };
        
        
        if ((same[0] != -1) && (same[0] == same[1])
            && (same[0] == same[2]) && (same[0] == same[3]))
        {
            const int iter = get_iterations(x0, y0);
            for (int i = y0 + 1; i < y1; i++)
                for (int j = x0 + 1; j < x1; j++)
                    set_iterations(j, i, iter);
        }
        else
        {
            const int xm = (x0 + x1) / 2;
            const int ym = (y0 + y1) / 2;
            
            /* Subdivide the area and solve each subarea.
             */
            if (divide_width && divide_height)
            {
                workdata t1, t2, t3, t4;
                t1.x0 = x0;
                t1.x1 = xm - 1;
                t1.y0 = y0;
                t1.y1 = ym - 1;
                t1.maximum_iterations = maximum_iterations;
                
                t2.x0 = xm;
                t2.x1 = x1;
                t2.y0 = y0;
                t2.y1 = ym - 1;
                t2.maximum_iterations = maximum_iterations;
                
                t3.x0 = x0;
                t3.x1 = xm - 1;
                t3.y0 = ym;
                t3.y1 = y1;
                t3.maximum_iterations = maximum_iterations;
                
                t4.x0 = xm;
                t4.x1 = x1;
                t4.y0 = ym;
                t4.y1 = y1;
                t4.maximum_iterations = maximum_iterations;
                
                EnterCriticalSection(&CS_queueAccess);
                work.push(t1);
                work.push(t2);
                work.push(t3);
                work.push(t4);
                CV_queueNotEmpty.Signal(4);
                LeaveCriticalSection(&CS_queueAccess);
            }
            else if (divide_width)
            {
                workdata t1, t2;
                
                t1.x0 = x0;
                t1.x1 = xm - 1;
                t1.y0 = y0;
                t1.y1 = y1;
                t1.maximum_iterations = maximum_iterations;
                
                t2.x0 = xm;
                t2.x1 = x1;
                t2.y0 = y0;
                t2.y1 = y1;
                t2.maximum_iterations = maximum_iterations;
                
                EnterCriticalSection(&CS_queueAccess);
                work.push(t1);
                work.push(t2);
                CV_queueNotEmpty.Signal(2);
                LeaveCriticalSection(&CS_queueAccess);
            }
            else if (divide_height)
            {
                workdata t1, t2;
                
                t1.x0 = x0;
                t1.x1 = x1;
                t1.y0 = y0;
                t1.y1 = ym - 1;
                t1.maximum_iterations = maximum_iterations;
                
                t2.x0 = x0;
                t2.x1 = x1;
                t2.y0 = ym;
                t2.y1 = y1;
                t2.maximum_iterations = maximum_iterations;
                
                EnterCriticalSection(&CS_queueAccess);
                work.push(t1);
                work.push(t2);
                CV_queueNotEmpty.Signal(2);
                LeaveCriticalSection(&CS_queueAccess);
            }
            else
                /* If the area is too small for any subdivisions, directly solve
                 * for each position.
                 */
                for (int i = y0 + 1; i < y1; i++)
                    solve_row(x0 + 1, x1 - 1, i, maximum_iterations);
        }
    } while (true);
    
    return 1;
}

void parallel_mandelbrot::solve(double x0, double y0, double x1, double y1, int max_iterations)
{
    x_base = x0;
    y_base = y0;
    x_step = (x1 - x0) / double(width);
    y_step = (y1 - y0) / double(height);
    
    /*Initialize*/
    reset_iterations();
    
    /*Get Number of Processors*/
    {
        SYSTEM_INFO info;
        GetSystemInfo(&info);
        ThreadCount = info.dwNumberOfProcessors;
        activeThreads = ThreadCount;
        printf("Using %i worker threads.\n", ThreadCount);
    }
    
    /*Generate Work*/
    {
        /*Begin subdivided into the number of threads we have
        This code was tested and shown to function at the same
        speed under all tested cases, but was slightly buggy at times.
        
        By adding a '/' before the '/*' this code will be enabled
        and the other version disabled.
        */
        /*
        const int Width = (width / ThreadCount) - 1;
        const int Height = height - 1;
        int mx = -1;
        for (unsigned int x = 0; x < ThreadCount; x++)
        {
            workdata t1;
            
            t1.x0 = (mx += 1);
            t1.x1 = (mx += Width);
            t1.y0 = 0;
            t1.y1 = Height;
            t1.maximum_iterations = max_iterations;
            
            work.push(t1);
        }
        /*/
        workdata t1;
        
        t1.x0 = 0;
        t1.x1 = width - 1;
        t1.y0 = 0;
        t1.y1 = height - 1;
        t1.maximum_iterations = max_iterations;
        
        work.push(t1);
        //*/
    }
    
    /*Generate Threads*/
    threads = new HANDLE[ThreadCount];
    for (unsigned int x = 0; x < ThreadCount; x++)
        threads[x] = HANDLE(_beginthreadex(0, 0, Worker, reinterpret_cast<void*>(this), 0, 0));
    
    /*Wait*/
    DWORD err = WaitForMultipleObjects(ThreadCount, threads, TRUE, INFINITE);
    if (err != 0)
    {
        DWORD num = GetLastError();
        printf("WaitForMultipleObjects() returned with error #%i.\n", num);
    }
    
    /*Clean-up*/
    for (unsigned int x = 0; x < ThreadCount; x++)
        CloseHandle(threads[x]);
    delete [] threads;
    threads = 0;
    ThreadCount = 0;
}