tbb41_20121003oss_win.zip_TBB-41_tbb_tbb41_tbb41_20121003oss_tbb

/* Copyright 2005-2012 Intel Corporation. All Rights Reserved. This file is part of Threading Building Blocks. Threading Building Blocks is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License version 2 as published by the Free Software Foundation. Threading Building Blocks is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with Threading Building Blocks; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA As a special exception, you may use this file as part of a free software library without restriction. Specifically, if other files instantiate templates or use macros or inline functions from this file, or you compile this file and link it with other files to produce an executable, this file does not by itself cause the resulting executable to be covered by the GNU General Public License. This exception does not however invalidate any other reasons why the executable file might be covered by the GNU General Public License. */ // Polygon overlay // #include <iostream> #include <algorithm> #include <string.h> #include <cstdlib> #include <assert.h> #include "tbb/tick_count.h" #include "tbb/blocked_range.h" #include "tbb/task_scheduler_init.h" #include "tbb/parallel_for.h" #include "tbb/mutex.h" #include "tbb/spin_mutex.h" #include "polyover.h" #include "polymain.h" #include "pover_video.h" using namespace std; /*! * @brief intersects a polygon with a map, adding any results to output map * * @param[out] resultMap output map (must be allocated) * @param[in] polygon to be intersected * @param[in] map intersected against * @param[in] lock to use when adding output polygons to result map * */ void OverlayOnePolygonWithMap(Polygon_map_t *resultMap, RPolygon *myPoly, Polygon_map_t *map2, tbb::spin_mutex *rMutex) { int r1, g1, b1, r2, g2, b2; int myr=0; int myg=0; int myb=0; int p1Area = myPoly->area(); for(unsigned int j=1; (j < map2->size()) && (p1Area > 0); j++) { RPolygon *p2 = &((*map2)[j]); RPolygon *pnew; int newxMin, newxMax, newyMin, newyMax; myPoly->getColor(&r1, &g1, &b1); if(PolygonsOverlap(myPoly, p2, newxMin, newyMin, newxMax, newyMax)) { p2->getColor(&r2, &g2, &b2); myr = r1 + r2; myg = g1 + g2; myb = b1 + b2; p1Area -= (newxMax-newxMin+1)*(newyMax - newyMin + 1); if(rMutex) { tbb::spin_mutex::scoped_lock lock(*rMutex); resultMap->push_back(RPolygon(newxMin, newyMin, newxMax, newyMax, myr, myg, myb)); } else { resultMap->push_back(RPolygon(newxMin, newyMin, newxMax, newyMax, myr, myg, myb)); } } } } /*! * @brief Serial version of polygon overlay * @param[out] output map * @param[in] first map (map that individual polygons are taken from) * @param[in] second map (map passed to OverlayOnePolygonWithMap) */ void SerialOverlayMaps(Polygon_map_t **resultMap, Polygon_map_t *map1, Polygon_map_t *map2) { cout << "SerialOverlayMaps called" << std::endl; *resultMap = new Polygon_map_t; RPolygon *p0 = &((*map1)[0]); int mapxSize, mapySize, ignore1, ignore2; p0->get(&ignore1, &ignore2, &mapxSize, &mapySize); (*resultMap)->reserve(mapxSize*mapySize); // can't be any bigger than this // push the map size as the first polygon, (*resultMap)->push_back(RPolygon(0,0,mapxSize, mapySize)); for(unsigned int i=1; i < map1->size(); i++) { RPolygon *p1 = &((*map1)[i]); OverlayOnePolygonWithMap(*resultMap, p1, map2, NULL); } } /*! * @class ApplyOverlay * @brief Simple version of parallel overlay (make parallel on polygons in map1) */ class ApplyOverlay { Polygon_map_t *m_map1, *m_map2, *m_resultMap; tbb::spin_mutex *m_rMutex; public: /*! * @brief functor to apply * @param[in] r range of polygons to intersect from map1 */ void operator()( const tbb::blocked_range<int> & r) const { PRINT_DEBUG("From " << r.begin() << " to " << r.end()); for(int i=r.begin(); i != r.end(); i++) { RPolygon *myPoly = &((*m_map1)[i]); OverlayOnePolygonWithMap(m_resultMap, myPoly, m_map2, m_rMutex); } } ApplyOverlay(Polygon_map_t *resultMap, Polygon_map_t *map1, Polygon_map_t *map2, tbb::spin_mutex *rmutex) : m_resultMap(resultMap), m_map1(map1), m_map2(map2), m_rMutex(rmutex) {} }; /*! * @brief apply the parallel algorithm * @param[out] result_map generated map * @param[in] polymap1 first map to be applied (algorithm is parallel on this map) * @param[in] polymap2 second map. */ void NaiveParallelOverlay(Polygon_map_t *&result_map, Polygon_map_t &polymap1, Polygon_map_t &polymap2) { // ----------------------------------- bool automatic_threadcount = false; if(gThreadsLow == THREADS_UNSET || gThreadsLow == tbb::task_scheduler_init::automatic) { gThreadsLow = gThreadsHigh = tbb::task_scheduler_init::automatic; automatic_threadcount = true; } result_map = new Polygon_map_t; RPolygon *p0 = &(polymap1[0]); int mapxSize, mapySize, ignore1, ignore2; p0->get(&ignore1, &ignore2, &mapxSize, &mapySize); result_map->reserve(mapxSize*mapySize); // can't be any bigger than this // push the map size as the first polygon, tbb::spin_mutex *resultMutex = new tbb::spin_mutex(); int grain_size = gGrainSize; for(int nthreads = gThreadsLow; nthreads <= gThreadsHigh; nthreads++) { tbb::task_scheduler_init init(nthreads); if(gIsGraphicalVersion) { RPolygon *xp = new RPolygon(0, 0, gMapXSize-1, gMapYSize-1, 0, 0, 0); // Clear the output space delete xp; } // put size polygon in result map result_map->push_back(RPolygon(0,0,mapxSize, mapySize)); tbb::tick_count t0 = tbb::tick_count::now(); tbb::parallel_for (tbb::blocked_range<int>(1,(int)(polymap1.size()),grain_size), ApplyOverlay(result_map, &polymap1, &polymap2, resultMutex)); tbb::tick_count t1 = tbb::tick_count::now(); double naiveParallelTime = (t1-t0).seconds() * 1000; cout << "Naive parallel with spin lock and "; if(automatic_threadcount) cout << "automatic"; else cout << nthreads; cout << ((nthreads == 1) ? " thread" : " threads"); cout << " took " << naiveParallelTime << " msec : speedup over serial " << (gSerialTime / naiveParallelTime) << std::endl; if(gCsvFile.is_open()) { gCsvFile << "," << naiveParallelTime; } #if _DEBUG CheckPolygonMap(result_map); ComparePolygonMaps(result_map, gResultMap); #endif result_map->clear(); } delete resultMutex; if(gCsvFile.is_open()) { gCsvFile << std::endl; } // ----------------------------------- } template<typename T> void split_at( Flagged_map_t& in_map, Flagged_map_t &left_out, Flagged_map_t &right_out, const T median) { left_out.reserve(in_map.size()); right_out.reserve(in_map.size()); for(Flagged_map_t::iterator i = in_map.begin(); i != in_map.end(); ++i ) { RPolygon *p = i->p(); if(p->xmax() < median) { // in left map left_out.push_back(*i); } else if(p->xmin() >= median) { right_out.push_back(*i); // in right map } else { // in both maps. left_out.push_back(*i); right_out.push_back(RPolygon_flagged(p, true)); } } } // range that splits the maps as well as the range. the