Parallel aspiration windows

[geko]

I implemented a simple aspiration window algorithm and it works well, at depth 1 searches for a full window and then perform 3 searches progressively opening window:

Code: Select all

 while (iterative deeping){
        depth++;

        if (depth == 1) {
            val = search(depth, -_INFINITE, _INFINITE);
        } else {
            tmp = search(depth, val - VAL_WINDOW, val + VAL_WINDOW);
            if &#40;tmp <= val - VAL_WINDOW || tmp >= val + VAL_WINDOW&#41; &#123;
                tmp = search&#40;depth, val - VAL_WINDOW * 2, val + VAL_WINDOW * 2&#41;;
            &#125;
            if &#40;tmp <= val - VAL_WINDOW * 2 || tmp >= val + VAL_WINDOW * 2&#41; &#123;
                tmp = search&#40;depth, val - VAL_WINDOW * 4, val + VAL_WINDOW * 4&#41;;
            &#125;
            if &#40;tmp <= val - VAL_WINDOW * 4 || tmp >= val + VAL_WINDOW * 4&#41; &#123;
                tmp = search&#40;depth, -_INFINITE, _INFINITE&#41;;
            &#125;
            val = tmp;
        &#125;
    &#125;

now i implemented the parallel algorithm, at depth >1 launching 3 threads one for each search and stop at the first positive research, but the result is poor (on many match).
I think the problem is the 3 overlapped windows,
should launch non-overlapping windows? How do I choose the edges?

[Dann Corbit]

Serially, the subsequent searches happen only when the aspiration window fails. I guess that if the window is not super-narrow, then the subsequent searches happen rarely.

In your parallel version, if you always launch three threads, then the searches always happen.

So it is not doing the same things and it is searching a lot more.

Unless I did not understand you clearly.

This seems to be what you are doing but the serial dependency is more clear:

Code: Select all

while (iterative deeping) {
    depth++;

    int fudge_factor = 2;
    int multiplier = 2;
    if (depth == 1) {
        val = search(depth, -_INFINITE, _INFINITE);
    } else {
        tmp = search(depth, val - VAL_WINDOW, val + VAL_WINDOW);
        int distance = std::abs(tmp - val);
        if (distance > VAL_WINDOW) {
            tmp = search(depth, val - distance * fudge_factor, val + distance * fudge_factor);
            distance = std::abs(tmp - val);
            if (distance > VAL_WINDOW) {
                fudge_factor *= multiplier;
                tmp = search(depth, val - distance * fudge_factor, val + distance * fudge_factor);
                distance = std::abs(tmp - val);
                if (distance > VAL_WINDOW) {
                    tmp = search(depth, -_INFINITE, _INFINITE);
                }
            }
        }
        val = tmp;
    }
}