pyocl/openclga

A Python Library for Genetic Algorithm on OpenCL

Join us on slack (歡迎上 slack 交流 !!) =============== .. figure:: https://img.shields.io/badge/slack-n.n-pink.svg :target: https://pyopenclopt.slack.com/

OpenCLGA

OpenCLGA is a python library for running genetic algorithm among Open CL devices, like GPU, CPU, DSP, etc. In the best case, you can run your GA parallelly at all of your Open CL devices which give you the maximum computing power of your machine. In the worse case, which you only have CPU, you still can run the code at parallel CPU mode.

We had implemented OpenCLGA at ocl_ga.py which encapsulate GA follow (population, crossover, mutation, fitness calculation). User could solve their problem by providing the fitness calculation function and run the code.

Please note that OpenCLGA is implemented at Python 3.5 or above. It should work at Python 2.x but it is not guaranteed.

Demo Video

Taiwan Travel example: https://youtu.be/4pqmuV8RkMg

Prerequisite: install PYOPENCL

Option A. Please refer to https://wiki.tiker.net/PyOpenCL to find your OS or

Option B. Install by ourself

• Windows 10 (just to install all required stuff in a quick way)
  • Step 1. Install platform opencl graphic driver, e.g. Intel CPU or Intel HD Grahics (https://software.intel.com/en-us/intel-opencl), NVIDIA GPU Driver (https://developer.nvidia.com/opencl)

  • Step 2. Install the following *.whl for python from

    1. http://www.lfd.uci.edu/~gohlke/pythonlibs/#numpy
    2. http://www.lfd.uci.edu/~gohlke/pythonlibs/#pyopencl

• Ubuntu 16.04

  • Step 1. Install platform OpenCL graphic driver, i.e.

    1. Intel CPU or Intel HD Graphics.
       1. OpenCL™ 2.0 GPU/CPU driver package(SRB_4.1) for Linux* (64-bit)
       2. Installation instructions.

  • Step 2. Download Intel SDK for Application (2016 R3)& ICDs and install, if you have Intel devices : :

    $> sudo apt-get install libnuma1 alien
    $> tar -xvf ./intel_sdk_for_opencl_2016_ubuntu_6.3.0.1904_x64.tgz
    $> cd ./intel_sdk_for_opencl_2016_ubuntu_6.3.0.1904_x64/rpm
    $> sudo alien opencl-2.1-intel-cpu-exp-6.3.0.1904-1.x86_64.rpm
    $> sudo dpkg -i opencl-2.1-intel-cpu-exp_6.3.0.1904-2_amd64.deb
    $> sudo apt-get install clinfo
    // To verify platform information from OpenCL
    $> clinfo

    You can verify the installed OpenCL driver is located in /opt/intel/ and the ICD loader is located in /etc/OpenCL/vendors.

  • Step 3. Create a virtual environment for pyopencl. :

    // Make sure dependencies for building wheel is available on system.
    $> sudo apt-get install build-essential libssl-dev libffi-dev python-dev
    $> sudo apt-get install python3-pip python3-venv python3-tk ocl-icd-*
    $> python3 -m venv [NameOfEnv]
    $> source ./NameOfEnv/bin/activate
    <NameOfEnv>$> pip3 install --upgrade pip
    <NameOfEnv>$> pip3 install pyopencl

  • Step 4. Verification :

    <NameOfEnv>$> python3
    > import pyopencl as cl
    > cl.create_some_context()

• Mac OS X

  • Step 1. Install Python3: since OpenCL drivers had already included in Mac OS X, we don't need to install any OpenCL driver by ourself. So, we can start from Python3. :

    $> brew update
    $> brew install python3
    $> pip3 install virtualenv

    Note that you may not need to install virtualenv if you already installed it with python 2.7.

  • Step 2. Create a virtual environment for pyopencl: before install pyopencl, we may need to install XCode developer console tool with xcode-select --install command. If you already had it, you don't need to run it. :

    $> python3 -m venv [NameOfEnv]
    $> source ./NameOfEnv/bin/activate
    <NameOfEnv>$> pip3 install --upgrade pip
    <NameOfEnv>$> pip3 install pycparser cffi numpy wheel
    <NameOfEnv>$> pip3 install pyopencl

  • Step 3. Verification. :

    <NameOfEnv>$> python3
    > import pyopencl as cl
    > cl.create_some_context()

Run OpenCLGA examples

1. Enter virtual env (optional):

• For Windows with MinGW environment. :

  $> source <NameOfEnv>/Scripts/activate

• For Linux/Mac OS X environment. :

  $> source ./NameOfEnv/bin/activate

2. Download the code from Github or git clone the repository via the following command. :

   <NameOfEnv>$> git clone https://github.com/PyOCL/OpenCLGA.git

3. Install Extra package (optional) :

• For Linux environment. :

  // To make matplotlib display correctly.
  $> sudo apt-get install python3-tk

4. Execute the code. :

   <NameOfEnv>$> pip3 install git+git://github.com/PyOCL/OpenCLGA.git
   <NameOfEnv>$> unzip OpenCLGA-master.zip
   <NameOfEnv>$> cd OpenCLGA-master
   <NameOfEnv>$> python3 examples/tsp/simple_tsp.py

NOTE : In external process mode, if "no device" exception happen during create_some_context(), Please set PYOPENCL_CTX=N (N is the device number you want by default) at first.

NOTE : Since we didn't publish this project to pipa. We need to install this project with source, `pip3 install .`.

openclga's Issues

add a new execution type: the total time GA can use

Implement Ant colony optimization algorithm based on PyOpenCL

We'd like to have a 2nd optimization algorithm to strengthen the ability of this module.

apply taiwan 319 cities to this project

elitism mode is not working

don't know why....

test and support UI viewer mode

As a user, I would like to have multiple web console to see the results. Only one can be the controller and others are viewer.

Elitism mode

as a user, I would like to share top N chromosomes among all devices to boost the performance.

enable travis for regression test once we have #13

As a user, I would like to know if this project is robust enough...

move oclGA to root

move UI out of OpenCLGA to be another repo

We should move the UI as a standalone repo and put the production code at ui folder.

introduce cross-compile tool to compile python code into cl code

We should evaluate py2opencl and help it to be compatible with python 3

reverse the min/max calculation

Currently, we use TSP as an example which tries to minimize the path. This doesn't follow the convention of GA. GA tries maximize the fitness value. We should reverse our implementation to follow the convention of GA.

add unit test

• python unit test
• opencl unit test

as a contributor, I would like to run the test cases before contributing my code to repo for preventing breaks.

Stabililize server/client socket connection

We could improve it in some parts.

1. Add heartbeat mechanism to keep server / client connection alive
2. Send/Recv data in {Server,Client} should be separate in different threads.
3. Considering epoll to improve performance.

[meta] generalize tsp_cl_algo as a GA algorithm

• separate crossover, mutation, fitness as three files
• implement non-repeatable crossover
• implement non-repeatable mutation
• implement repeatable crossover
• implement repeatable mutation
• generate gene/chromosome struct according to gene.py and chromoosome.py
• generate kernel entry function according to properties of algorithm.py.
  • crossover function,
  • mutation function, etc

Improve UI performance

We use main-thread to handle all messages from websocket. It would be nice to handle the data at batch. Because the message from web worker may be too fast that a redux cannot handle it with clone or immutable structure. We can aggregate some of them and process them in a batch.

try to use pyopencl -D to define preprocess definitions.

kilik had found a way to define preprocessor definition at python, see #9 .

size = 100
clProg = cl.Program(ctx, fstr).build(options="-D GLOBAL_SIZE={0}".format(size))

Currently, we use code generation to put all preprocessor definitions. If possible, we should use build options to do so. I cannot make sure how long it can use or any limitation at that.

support web server public folder

As a user, I would like to specify the web server of ocl_ga_server to populate the web client I want to populate.

add pause, memory dump, memory restore, and continue feature

As a user, I would like to pause the execution of GA for closing my computer and find a good time to resume the execution of GA.

rename the function names

Some functions at utils do the generic things, like custom_crossover does non-repeatable element cross over. We should rename all of them to reflect their intrinsic.

distributed GA

As a user, I would like to connect all of my devices to run a single GA model.

charts at UI

• We need detail performance chart of each device
• We need overall performance chart accumulated by time, 5 sec by default.

Block connections when server is preparing and resume it after server is stopped

We shouldn't accept more connections when UI dispatches a prepare command because we cannot run, pause, stop any clients if they didn't prepared.

We can accept more connection when the server is created or all clients are stopped. In the client stopped, we can recycle the client by prepare them again....

Make statistic information best/worst be able to track more.

Should consider it as a list or dictionary, so that we could track the top N best chromosomes, or the bottom M worst chromosomes.

worker disconnected is not dispatched when we use ctrl+c to stop it

[server_loop] TaskThread : start executing ... task (1)
[httpwsserver] TaskThread : running ...
[INFO] Http server is created @ port 8000.
adding task(2) to ...[httpwsserver]
[httpwsserver] TaskThread : start executing ... task (2)
Press prepare    + <Enter> to prepare
Press run        + <Enter> to run
Press restore    + <Enter> to restore
Press pause      + <Enter> to pause
Press save       + <Enter> to save (filename:test%d%d.pickle)
Press stop       + <Enter> to stop
Press get_st     + <Enter> to get statistics
Press get_best   + <Enter> to get best
Press ctrl       + c       to exit
trying to access /Users/hchu/git/python/oclGA/OpenCLGA/ui
127.0.0.1 - - [13/May/2017 23:19:11] "GET / HTTP/1.1" 200 -
trying to access /Users/hchu/git/python/oclGA/OpenCLGA/ui/static/js/main.c1e1ba0d.js
trying to access /Users/hchu/git/python/oclGA/OpenCLGA/ui/static/css/main.5da4bf40.css
127.0.0.1 - - [13/May/2017 23:19:11] "GET /static/js/main.c1e1ba0d.js HTTP/1.1" 200 -
127.0.0.1 - - [13/May/2017 23:19:11] "GET /static/css/main.5da4bf40.css HTTP/1.1" 200 -
127.0.0.1 - - [13/May/2017 23:19:12] "GET / HTTP/1.1" 101 -
127.0.0.1 - - [13/May/2017 23:19:12] websocket connected
[INFO] WS Controller ('127.0.0.1', 52757) is on !! 
trying to access /Users/hchu/git/python/oclGA/OpenCLGA/ui/favicon-16x16.png
127.0.0.1 - - [13/May/2017 23:19:12] "GET /favicon-16x16.png HTTP/1.1" 200 -
trying to access /Users/hchu/git/python/oclGA/OpenCLGA/ui/favicon-96x96.png
127.0.0.1 - - [13/May/2017 23:19:12] "GET /favicon-96x96.png HTTP/1.1" 200 -
trying to access /Users/hchu/git/python/oclGA/OpenCLGA/ui/favicon-32x32.png
127.0.0.1 - - [13/May/2017 23:19:12] "GET /favicon-32x32.png HTTP/1.1" 200 -
trying to access /Users/hchu/git/python/oclGA/OpenCLGA/ui/android-icon-192x192.png
127.0.0.1 - - [13/May/2017 23:19:12] "GET /android-icon-192x192.png HTTP/1.1" 200 -
[('127.0.0.1', 52775)] Connected !
[('127.0.0.1', 52776)] Connected !
[INFO] Send to Controller : {'type': 'workerConnected', 'data': {'type': 'CPU', 'platform': 'Apple', 'name': 'Intel(R) Core(TM) i7-3540M CPU @ 3.00GHz', 'ip': '127.0.0.1', 'worker': '988169d037ef11e784f0542696d3ed23'}}
[INFO] Send to Controller : {'type': 'workerConnected', 'data': {'type': 'GPU', 'platform': 'Apple', 'name': 'HD Graphics 4000', 'ip': '127.0.0.1', 'worker': '9882e29c37ef11e78dab542696d3ed23'}}
[('127.0.0.1', 52786)] Connected !
[INFO] Send to Controller : {'type': 'workerConnected', 'data': {'type': 'CPU', 'platform': 'Apple', 'name': 'Intel(R) Core(TM) i7-3540M CPU @ 3.00GHz', 'ip': '127.0.0.1', 'worker': 'b2ea153837ef11e79efa542696d3ed23'}}
[('127.0.0.1', 52796)] Connected !
[INFO] Send to Controller : {'type': 'workerConnected', 'data': {'type': 'CPU', 'platform': 'Apple', 'name': 'Intel(R) Core(TM) i7-3540M CPU @ 3.00GHz', 'ip': '127.0.0.1', 'worker': 'c6bff50037ef11e7a961542696d3ed23'}}
trying to access /Users/hchu/git/python/oclGA/OpenCLGA/ui/static/js/main.c1e1ba0d.js.map
127.0.0.1 - - [13/May/2017 23:21:10] "GET /static/js/main.c1e1ba0d.js.map HTTP/1.1" 200 -
trying to access /Users/hchu/git/python/oclGA/OpenCLGA/ui/static/css/main.5da4bf40.css.map
127.0.0.1 - - [13/May/2017 23:21:10] "GET /static/css/main.5da4bf40.css.map HTTP/1.1" 200 -
trying to access /Users/hchu/git/python/oclGA/OpenCLGA/ui
127.0.0.1 - - [13/May/2017 23:21:33] "GET / HTTP/1.1" 200 -
[INFO] WS Controller is off, clean up all websockets !! 
127.0.0.1 - - [13/May/2017 23:21:33] websocket closed
127.0.0.1 - - [13/May/2017 23:21:34] "GET / HTTP/1.1" 101 -
127.0.0.1 - - [13/May/2017 23:21:34] websocket connected
[INFO] WS Controller ('127.0.0.1', 52906) is on !! 
[INFO] Send to Controller : {'type': 'workerConnected', 'data': {'type': 'CPU', 'platform': 'Apple', 'name': 'Intel(R) Core(TM) i7-3540M CPU @ 3.00GHz', 'ip': '127.0.0.1', 'worker': '988169d037ef11e784f0542696d3ed23'}}
[INFO] Send to Controller : {'type': 'workerConnected', 'data': {'type': 'GPU', 'platform': 'Apple', 'name': 'HD Graphics 4000', 'ip': '127.0.0.1', 'worker': '9882e29c37ef11e78dab542696d3ed23'}}
[INFO] Send to Controller : {'type': 'workerConnected', 'data': {'type': 'CPU', 'platform': 'Apple', 'name': 'Intel(R) Core(TM) i7-3540M CPU @ 3.00GHz', 'ip': '127.0.0.1', 'worker': 'b2ea153837ef11e79efa542696d3ed23'}}
[INFO] Send to Controller : {'type': 'workerConnected', 'data': {'type': 'CPU', 'platform': 'Apple', 'name': 'Intel(R) Core(TM) i7-3540M CPU @ 3.00GHz', 'ip': '127.0.0.1', 'worker': 'c6bff50037ef11e7a961542696d3ed23'}}

add more performance index for GA

As a user, I would like to see the performance of each generation. It would be ok to see it at console. But it would be great to see it as a GUI chart.

Move statistic information best/avg/worst into ocl_ga

These information should be independent from chromosome.

Update README.md

The README.md still use TSP. We should rename them...

rename project name to something related to GA

TSP is a problem name not a good name for GA. We should replace it with another name.

I would suggest:

• clGA
• oclGA
• GAGPU
• PyGAGPU
• pyGG

Implement common chromosome

To support mulit-types of genes

repack oclGA as a python module

as a user, I would like to use python setup.py to install all dependencies and download it through pip...

controller no response while we use small population

It looks like the reducer cannot handle a lot of data... The possible solutions may be 1. move data cloning, aggregation, comparison to another thread, 2. use a time interval for batch data processing.

Implement different mutation methods in simple_gene

SomeFeatures

Hello,

This is an interesting project. Some questions:

1. How PyOpenCL compatible with NVidia Card ?

2. Is the objective function "converted/implemented" on the GPU side (evaluation is done on GPU) ?

Thanks, regards

extinction mode

As a user, I would like to extinct some chromosomes if they are too similar to each other.

Make "MessageHandler.sendq" thread-safe.

We're append data to sendq in A thread but consuming sendq in B thread.
Even further, now we check the length of sendq to decide if the socket is ok to be closed.

We should make it thread-safe.

Support Simulated Annealing Algorithm (Python Version)

Provide an implementation in python.

add more early termination criteria

As a user, I would like to terminate the calculation if one the following cases:

• the best solution keeps the same after Nth generations
• the maximum time that I can wait
• expected fitness value found

Exception Tcl_AsyncDelete: async handler deleted by the wrong thread

Exception ignored in: <bound method Image.__del__ of <tkinter.PhotoImage object at 0x000001FA57641668>>
Traceback (most recent call last):
  File "D:\Program Files\Python35\lib\tkinter\__init__.py", line 3356, in __del__
    self.tk.call('image', 'delete', self.name)
RuntimeError: main thread is not in main loop
Tcl_AsyncDelete: async handler deleted by the wrong thread

Block connection when websocket is used

As a user of UI, we should block the connection when websocket is connected by one UI to prevent other users uses the server.

Map cities to open street map

ref:
https://wiki.openstreetmap.org/wiki/Routing#End_users:_Routing_software

evaluate if we can generate code and do type casting on the fly

According to the proposal 1 and 2, we should generate some PIs or codes on the fly. This part is doable. But we need to evaluate if we can cast __global variable into what we want....

This issue is just for evaluation, no need to commit any code.

add multiple local/remove device support to taiwan travel example

Since kilik had a remote device execution lib, we can leverage it to run oclGA among all of our devices to see who fast/best we can have.

• server
• client
• UI

more documents and wikis

it's time to write docs more than codes.

• comments of codes
  • python (@kilikkuo)
  • cl (@john-hu)
• getting started (add distributed mode, install and run our example) (@kilikkuo)
• tutorial: how to write a GA application with OpenCLGA (write a new code) (@john-hu)
• home page with jekyll
• API doc (if possible, doxygen)

move tsp.py and taiwan_travel_319.py to examples folder

• tsp
• taiwan_travel_319