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)
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)
TARGET_LINK_LIBRARIES(germs ${GENELIBS})
+
SUBDIRS(test)
SET(TESTSRC geneordertest genealgorithmstest modelidentifiertest
- genesortertest componenttreetest)
+ genesortertest componenttreetest threadgenesortertest)
CHECK_INCLUDE_FILE_CXX("cppunit/TestFixture.h" HAVE_CPPUNIT)
--- /dev/null
+#include <cppunit/TestFixture.h>
+#include <cppunit/extensions/HelperMacros.h>
+
+#include <threadgenesorter.h>
+#include <geneorder.h>
+#include <genealgorithms.h>
+#include <reverseaction.h>
+#include <models.h>
+#include <model.h>
+
+#include <algorithm>
+#include <iterator>
+
+#include <iostream>
+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<int> _validPerm;
+ vector<int> _validPerm2;
+ vector<int> _validPerm3;
+ vector<int> _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
--- /dev/null
+/***************************************************************************
+ * 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<pthread_t> 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<ExecutionStuff*>(arg);
+ es->_sorter->sorter(es->_go);
+ delete es;
+ pthread_exit((void*)0);
+}
+
+void* t_worker(void* arg){
+ ThreadGeneSorter* sorter = static_cast<ThreadGeneSorter*>(arg);
+ sorter->worker();
+ pthread_exit((void*)0);
+}
--- /dev/null
+/***************************************************************************
+ * 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 <pthread.h>
+
+#include <queue>
+#include <vector>
+#include <utility>
+
+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<typename T>
+ bool operator()(T s1, T s2){
+ return s1.first < s2.first;
+ }
+ };
+ typedef std::priority_queue<std::pair<double,ActionList>,std::vector<std::pair<double,ActionList> >, 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<SortUnit> 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
projects / germs.git / commitdiff