From: Michael Andreen Date: Sun, 26 Oct 2008 17:16:11 +0000 (+0100) Subject: Initial thread infrastructure and test X-Git-Url: https://ruin.nu/git/?p=germs.git;a=commitdiff_plain;h=623097444fac1993a86e6d73b203bc3c6d731c11 Initial thread infrastructure and test --- diff --git a/CMakeLists.txt b/CMakeLists.txt index 4bcedaf..01f2615 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -1,5 +1,7 @@ PROJECT(GERMS) +cmake_minimum_required(VERSION 2.6) + SET(CMAKE_VERBOSE_MAKEFILE OFF) SET(EXECUTABLE_OUTPUT_PATH ${PROJECT_BINARY_DIR}/bin) SET(LIBRARY_OUTPUT_PATH ${PROJECT_BINARY_DIR}/lib) diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 9bdaf40..6b5217e 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -3,28 +3,31 @@ INCLUDE(CheckIncludeFileCXX) SET(CMAKE_VERBOSE_MAKEFILE OFF) -#ADD_DEFINITIONS(-Wall -O2) +#ADD_DEFINITIONS(-Wall -O2 -D__GTHREADS -D_REENTRANT +# -D_POSIX_PTHREAD_SEMANTICS -pthread) #ADD_DEFINITIONS(-Wall -pedantic -g -D_GLIBCXX_DEBUG) -ADD_DEFINITIONS(-Wall -pedantic -g) +ADD_DEFINITIONS(-Wall -pedantic -g -D__GTHREADS -D_REENTRANT + -D_POSIX_PTHREAD_SEMANTICS -pthread) #INCLUDE(CheckCXXSourceCompiles) INCLUDE_DIRECTORIES(.) ADD_LIBRARY(GeneSort geneorder genealgorithms modelidentifier genesorter model - models componenttree) + models componenttree threadgenesorter) ADD_EXECUTABLE(germs main.cpp) +FIND_PACKAGE(Threads REQUIRED) CHECK_INCLUDE_FILE("doublefann.h" HAVE_FANN) +SET(GENELIBS GeneSort ${CMAKE_THREAD_LIBS_INIT}) IF (HAVE_FANN) - SET(GENELIBS doublefann GeneSort) + LIST(APPEND GENELIBS doublefann) ELSE(HAVE_FANN) INCLUDE_DIRECTORIES(. ${CMAKE_SOURCE_DIR}/fann/src/include) ADD_LIBRARY(doublefann ${CMAKE_SOURCE_DIR}/fann/src/doublefann.c) TARGET_LINK_LIBRARIES(GeneSort doublefann) - SET(GENELIBS GeneSort) ENDIF(HAVE_FANN) @@ -41,4 +44,5 @@ ENDIF(HAVE_TR1) TARGET_LINK_LIBRARIES(germs ${GENELIBS}) + SUBDIRS(test) diff --git a/src/test/CMakeLists.txt b/src/test/CMakeLists.txt index 02a0dce..aabcbde 100644 --- a/src/test/CMakeLists.txt +++ b/src/test/CMakeLists.txt @@ -8,7 +8,7 @@ SET(CMAKE_VERBOSE_MAKEFILE OFF) SET(TESTSRC geneordertest genealgorithmstest modelidentifiertest - genesortertest componenttreetest) + genesortertest componenttreetest threadgenesortertest) CHECK_INCLUDE_FILE_CXX("cppunit/TestFixture.h" HAVE_CPPUNIT) diff --git a/src/test/threadgenesortertest.cpp b/src/test/threadgenesortertest.cpp new file mode 100644 index 0000000..58d4893 --- /dev/null +++ b/src/test/threadgenesortertest.cpp @@ -0,0 +1,110 @@ +#include +#include + +#include +#include +#include +#include +#include +#include + +#include +#include + +#include +using namespace std; + +/* + * A test case that is designed to produce + * example errors and failures. + * + */ + +#define TESTNAME ThreadGeneSorterTest + + +class TESTNAME : public CPPUNIT_NS::TestFixture +{ + CPPUNIT_TEST_SUITE( TESTNAME ); + CPPUNIT_TEST( testCreate ); + CPPUNIT_TEST( testSort ); + CPPUNIT_TEST_SUITE_END(); + +protected: + vector _validPerm; + vector _validPerm2; + vector _validPerm3; + vector _validPerm4; + +public: + + void setUp (){ + int validPerm[] = {1,2,3,4}; + _validPerm.assign(validPerm,validPerm+4); + int validPerm2[] = {1,-3,-2,4}; + _validPerm2.assign(validPerm2,validPerm2+4); + int validPerm3[] = {0,-2,-1,4,3,5,-8,6,7,9}; + _validPerm3.assign(validPerm3,validPerm3+10); + int validPerm4[] = {-3,1,2,4,6,5,7,-15,-13,-14,-12,-10,-11,-9,8}; + _validPerm4.assign(validPerm4,validPerm4+15); + + } + +protected: + + void testCreate (){ + ThreadGeneSorter so(Model(new Models::ModelImpl)); + so = so; + } + void testSort (){ + ThreadGeneSorter so(Model(new Models::ModelImpl), 3); + GeneOrder go(_validPerm.begin(),_validPerm.end()); + so.start(go); + so.join(); + ThreadGeneSorter::SolutionsQueue sq = so.solutions(); + CPPUNIT_ASSERT_EQUAL((size_t)1u,sq.size()); + GeneSorter::ActionList al = sq.top().second; + CPPUNIT_ASSERT_EQUAL((size_t)0u,al.size()); + + GeneOrder go2(_validPerm2.begin(),_validPerm2.end()); + so.start(go2); + so.join(); + sq = so.solutions(); + CPPUNIT_ASSERT_EQUAL((size_t)1u,sq.size()); + al = sq.top().second; + CPPUNIT_ASSERT_EQUAL((size_t)1u,al.size()); + CPPUNIT_ASSERT(sq.top().second[0] == ReverseAction(2,3)); + + sq.top().second[0](go2); + CPPUNIT_ASSERT(equal(go.begin(),go.end(),go2.begin())); + + GeneOrder go3(_validPerm3.begin(),_validPerm3.end()); + so.start(go3); + so.join(); + sq = so.solutions(); + CPPUNIT_ASSERT_EQUAL((size_t)24u,sq.size()); + al = sq.top().second; + CPPUNIT_ASSERT_EQUAL((size_t)5u,al.size()); + for (size_t i = 0; i < al.size(); ++i) + al[i](go3); + int perm[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}; + CPPUNIT_ASSERT(equal(go3.begin(),go3.end(),perm)); + + GeneOrder go4(_validPerm4.begin(),_validPerm4.end()); + + so.start(go3); + so.join(); + sq = so.solutions(); + CPPUNIT_ASSERT_EQUAL((size_t)1u,sq.size()); + al = sq.top().second; + CPPUNIT_ASSERT_EQUAL((size_t)13u,al.size()); + for (size_t i = 0; i < al.size(); ++i) + al[i](go4); + CPPUNIT_ASSERT(equal(go3.begin(),go3.end(),perm)); + + } +}; + +CPPUNIT_TEST_SUITE_REGISTRATION( TESTNAME ); + +#undef TESTNAME diff --git a/src/threadgenesorter.cpp b/src/threadgenesorter.cpp new file mode 100644 index 0000000..a45988c --- /dev/null +++ b/src/threadgenesorter.cpp @@ -0,0 +1,163 @@ +/*************************************************************************** + * Copyright (C) 2008 by Michael Andreen * + * andreen@student.chalmers.se * + * * + * This program is free software; you can redistribute it and/or modify * + * it under the terms of the GNU General Public License as published by * + * the Free Software Foundation; either version 2 of the License, or * + * (at your option) any later version. * + * * + * This program 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 this program; if not, write to the * + * Free Software Foundation, Inc., * + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA * + ***************************************************************************/ + +#include "threadgenesorter.h" +#include "sortaction.h" + +using namespace std; + +/** + * Handles locking and unlocking of mutexes. + * + * RAII style class for mutex acquisition. + */ +class Mutex { + pthread_mutex_t* _m; + bool _locked; + public: + Mutex(pthread_mutex_t* m){ + _m = m; + pthread_mutex_lock(_m); + _locked = true; + } + void unlock(){ + pthread_mutex_unlock(_m); + _locked = false; + } + ~Mutex(){ + if (_locked) + unlock(); + } +}; + +struct ExecutionStuff { + ExecutionStuff(ThreadGeneSorter* so, const GeneOrder& go): _sorter(so) + ,_go(go){}; + ThreadGeneSorter* _sorter; + GeneOrder _go; +}; + + +ThreadGeneSorter::ThreadGeneSorter(const Model& m, int threads) : _model(m){ + _workers = threads; + pthread_mutex_init(&_queuelock, NULL); + pthread_mutex_init(&_solutionslock, NULL); + pthread_cond_init(&_addedSolution,NULL); + pthread_cond_init(&_addedTask,NULL); + pthread_cond_init(&_waiting,NULL); +} + +void ThreadGeneSorter::join(){ + pthread_join(_tid,NULL); +} + +void ThreadGeneSorter::stop(){ + _done = true; +} + +size_t ThreadGeneSorter::size(){ + //TODO: thread safety.. + return _solutions.size(); +} + +double progress(int time, int solutions = 1){ +} + +ThreadGeneSorter::SolutionsQueue ThreadGeneSorter::solutions(){ + //TODO: thread safety.. + return _solutions; +} + +void ThreadGeneSorter::start(const GeneOrder& go){ + pthread_attr_t tattr; + pthread_attr_init(&tattr); + pthread_attr_setscope(&tattr, PTHREAD_SCOPE_SYSTEM); + ExecutionStuff* es = new ExecutionStuff(this,go); + pthread_create(&_tid, &tattr, t_sorter, es); +} + +void ThreadGeneSorter::sorter(const GeneOrder& go){ + _queue.push(SortUnit(0.0,go,ActionList())); + pthread_attr_t tattr; + pthread_attr_init(&tattr); + pthread_attr_setscope(&tattr, PTHREAD_SCOPE_SYSTEM); + _done = false; + _queue = SortQueue(); + _solutions = SolutionsQueue(); + + queue threads; + + _queue.push(SortUnit(0.0,go,ActionList())); + + int workers = _workers; + while (!_done){ + if (workers){ + --workers; + pthread_t tid; + pthread_create(&tid, &tattr, t_worker, this); + threads.push(tid); + }else{ + Mutex m(&_queuelock); + while(_workers != 0 && !_done){ + pthread_cond_wait(&_waiting,&_queuelock); + } + if (_workers == 0) + _done = true; + } + } + pthread_cond_broadcast(&_addedTask); + while(threads.size() > 0){ + pthread_join(threads.front(),NULL); + threads.pop(); + } + pthread_exit((void*)0); +} + +void ThreadGeneSorter::worker(){ + while(!_done){ + Mutex m(&_queuelock); + + while (_queue.size() == 0 && !_done){ + --_workers; + pthread_cond_signal(&_waiting); + pthread_cond_wait(&_addedTask,&_queuelock); + ++_workers; + } + if (_done) + break; + + SortUnit su = _queue.top(); + _queue.pop(); + m.unlock(); + } +} + +void* t_sorter(void* arg){ + ExecutionStuff* es = static_cast(arg); + es->_sorter->sorter(es->_go); + delete es; + pthread_exit((void*)0); +} + +void* t_worker(void* arg){ + ThreadGeneSorter* sorter = static_cast(arg); + sorter->worker(); + pthread_exit((void*)0); +} diff --git a/src/threadgenesorter.h b/src/threadgenesorter.h new file mode 100644 index 0000000..57d1052 --- /dev/null +++ b/src/threadgenesorter.h @@ -0,0 +1,136 @@ +/*************************************************************************** + * Copyright (C) 2008 by Michael Andreen * + * andreen@student.chalmers.se * + * * + * This program is free software; you can redistribute it and/or modify * + * it under the terms of the GNU General Public License as published by * + * the Free Software Foundation; either version 2 of the License, or * + * (at your option) any later version. * + * * + * This program 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 this program; if not, write to the * + * Free Software Foundation, Inc., * + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA * + ***************************************************************************/ + +#ifndef __THREADGENESORTER_H__ +#define __THREADGENESORTER_H__ + +#include "genesorter.h" +#include "geneorder.h" +#include "model.h" + +#include + +#include +#include +#include + +extern "C" void* t_sorter(void* arg); +extern "C" void* t_worker(void* arg); + +/** + * Finding the set of all possible sorting sequences. + * + * \author Michael Andreen + */ +class ThreadGeneSorter : public GeneSorter{ + friend void* t_sorter(void* arg); + friend void* t_worker(void* arg); + public: + + struct ScoreCmp { + template + bool operator()(T s1, T s2){ + return s1.first < s2.first; + } + }; + typedef std::priority_queue,std::vector >, ScoreCmp > SolutionsQueue; + + struct SortUnit{ + double _score; + GeneOrder _go; + ActionList _al; + SortUnit(double score,const GeneOrder& go,const ActionList& al) : _score(score),_go(go),_al(al){} + bool operator<(const SortUnit& su) const{ + return _score < su._score; + } + }; + + /** + * Creates a new threaded GeneSorter. + * + * \param threads The number of worker threads that you want to spawn. + */ + ThreadGeneSorter(const Model& m, int threads = 2); + + /** + * Takes a GeneOrder, and Model. + * + * Starts the work to find all possible sorting sequences. + */ + void start(const GeneOrder& go); + + /** + * Wait for sorter to end. + */ + void join(); + + /** + * Tell the sorter to stop execution. + */ + void stop(); + + /** + * Number of possible solutions. + */ + size_t size(); + + /** + * Waits for progress. + * + * \param time Max time to wait for. + * \param solutions The minimum number of solutions we'll wait for. + */ + double progress(int time, int solutions = 1); + + /** + * Get the full list of solutions. + */ + SolutionsQueue solutions(); + + ~ThreadGeneSorter(){}; + + private: + + void sorter(const GeneOrder& go); + void worker(); + + typedef std::priority_queue SortQueue; + //! Queue for possible sort alternatives. + SortQueue _queue; + //! List of full sort sequences. + SolutionsQueue _solutions; + + bool _done; + + int _workers; + + Model _model; + + pthread_mutex_t _queuelock; + pthread_mutex_t _solutionslock; + + pthread_cond_t _addedSolution; + pthread_cond_t _waiting; + pthread_cond_t _addedTask; + + pthread_t _tid; +}; + +#endif