Information retrieval, Search and recommendation engine:

Natural language processing:

https://class.coursera.org/nlp/lecture – Processing of texts written in ordinal languages
https://company.yandex.com/technologies/matrixnet.xml – search algorithm by Yandex
http://www.quora.com/What-is-the-search-algorithm-used-by-the-Google-search-engine-What-is-its-complexity

Information retrieval:

http://nlp.stanford.edu/IR-book/html/htmledition/irbook.html – Introduction to Information Retrieval, Cambridge
http://stackoverflow.com/questions/25803267/retrieve-topic-word-array-document-topic-array-from-lda-gensim
http://stats.stackexchange.com/questions/89356/document-similarity-gensim
http://machinelearning.wustl.edu/mlpapers/paper_files/BleiNJ03.pdf – Latent Dirichlet Allocation (LDA)
http://radar.oreilly.com/2015/02/topic-models-past-present-and-future.html
http://en.wikipedia.org/wiki/Topic_model

Few examples of applications for the above:

http://graus.nu/tag/gensim/
https://github.com/sandinmyjoints/gensimtalk/blob/master/gensim_example.py
http://stackoverflow.com/questions/27032517/what-does-the-output-vector-of-a-word-in-word2vec-represent
https://github.com/sandinmyjoints/gensimtalk/blob/master/gensim_example.py
http://stats.stackexchange.com/questions/89356/document-similarity-gensim
http://stackoverflow.com/questions/6486738/clustering-using-latent-dirichlet-allocation-algo-in-gensim

Recommender systems:

https://www.coursera.org/learn/recommender-systems/ – video lectures – 101 for Recommendation System
http://www.ibm.com/developerworks/library/os-recommender1/ – introduction to approach and algorithms
http://www.cs.bme.hu/nagyadat/Recommender_systems_handbook.pdf – “Encyclopedia” of recommender systems
http://www.slideshare.net/xamat/kdd-2014-tutorial-the-recommender-problem-revisited – overview of recommendation algorithms
http://www.machinelearning.org/proceedings/icml2007/papers/407.pdf – Restricted Boltzmann Machines for Collaborative Filtering
http://wiki.hsr.ch/Datenbanken/files/Recommender_System_for_Geo_MSE_DB_Seminar_HS2013_Senn_Paper_final.pdf

Ready for use recommendation engine:

https://cloud.google.com/prediction/ – Google recommendation engine
https://mahout.apache.org – Apache recommendation and general purpose machine learning framework

Elastic Search – just a few useful snippets

Install head plugin or rely on oldschool curl utility in order to test your queries:

curl -XPOST 'http://ELASTICSEARCH_HOST:ELASTICSEARCH_PORT/INDEX_NAME/_search?pretty' -d 'PUT_PROPER_QUERY_HERE'

or

curl -XPOST 'http://ELASTICSEARCH_HOST:ELASTICSEARCH_PORT/INDEX_NAME/_search?pretty' -d@FILE_WITH_YOUR_JSON_REQUEST

Q: Show me example of query for complex, nested document?

A:

{ "query": 
    { "bool":
        { "must": [
            {"nested":
                 {"path": "document.sub_document",
                  "query": 
                       {"bool": 
                           {"must": [
                               { "match":
                                   { "document.sub_document.attribute": "PUT_YOUR_SEARCH_VALUE_HERE" }
                               }
                           ]}
                        }
                 }
           }]
        }
    }
}

NOTE: if what are you searching for in sub-sub-sub document – just add proper number of nested chains of “bool” “must” “nested” elements.

Q: I need full text search and aggregations (aka facets) by attribute in nested document.

A:

{ "query": 
    { "query_string": 
        { "query": "PUT_YOUR_SEARCH_STRING_HERE" }
    },
    "aggs":
        {"name_of_parent_aggregation":
            {"nested":
                {"path": "document.SUB_DOCUMENT"},
                    "aggs":
                    {"name_of_aggregation":
                        {"terms":
                            {"field": "document.SUB_DOCUMENT.ATTRIBUTE_NAME"}
                        }
                    }
            }
        }
}

Q: I need a full text search and aggregations by geo positions aka distance range.

NOTE: put proper values for “origin”, “field”, “ranges” fields.

{ "query":
    { "query_string":
        { "query": "PUT_YOUR_SEARCH_STRING_HERE" }
    },
    "aggs":
        {"name_of_parent_aggregation":
            {"nested":
                {"path": "document.SUB_DOCUMENT"},
                "aggs": 
                    {"name_of_aggregation":
                        {"geo_distance":
                            {"origin": "100500, 100500",
                            "field":"document.SUB_DOCUMENT.NAME_OF_YOUR_GEO_POINT_ATTRIBUTE",
                             "ranges": [{"to": 1000}, {"to": 3000, "from": 1000}, {"from": 3000}]
                             }
                         }
                    }
            }
        }
}

Q: I have fields in document that contains multiple words, I want them to be be aggregated not as separate single terms, but as a whole string.

A.1 put proper mapping for such field – “multi_field” or in most recent version of elasticsearch – just “fields”.


... document mapping, ...

YOUR_FIELD: {   "type": "string",
                "fields":
                {"raw":
                    { "type": "string", "index": "not_analyzed" }
                }
            }

... document mapping, ...

A.2 use such kind of queries for nested faceting:

{"query":
    {"query_string":
        {"query": "PUT_YOUR_SEARCH_STRING_HERE"}
    },
    "aggs":
        {"name_of_parent_aggregation": 
            {"nested":
                {"path": "document.SUB_DOCUMENT"},
                 "aggs":
                     {"name_of_aggregation":
                         {"terms":
                             {"field": "document.SUB_DOCUMENT.ATTRIBUTE_NAME.raw"}
                         }
                     }
            }
        }
}

Q: I want return all documents sorted by distance and my geo_point field in nested document.

NOTE: ATTRIBUTE_NAME should be mapped as geo_point at moment of writing – it can be done only via manually created mapping.

A:

{"query":
    {"match_all": {}},
    "sort": [
        {"_geo_distance": 
            {"document.SUB_DOCUMENT.ATTRIBUTE_NAME": 
                {"lat": 25,"lon": 55},
                 "order": "asc",
                 "unit": "km",
                 "distance_type": "plane"
            }
        }]
}

Q: I want to return aggregation only?

A:

{"size": 0,
    "aggs": {
        "name_of_1st_parent_aggregation": {
            "nested": {"path": "document.SUB_DOCUMENT"},
            "aggs": {
                "name_of_1st_aggregation": {
                    "terms": {
                        "field":"document.SUB_DOCUMENT.ATTRIBUTE_NAME"
        }}}},
        "name_of_2nd_parent_aggregation": {
            "nested": {"path": "document.SUB_DOCUMENT_1"},
            "aggs": {
                "name_of_2nd_aggregation": {
                    "terms": {
                        "field":"document.SUB_DOCUMENT_1.ATTRIBUTE_NAME_1.raw"
        }}}},
        "name_of_3rd_parent_aggregation": {
            "nested": {"path": "document.SUB_DOCUMENT_2"},
            "aggs": {
                "name_of_3rd_aggregation": {
                    "geo_distance":
                            {"origin": "100500, 100500",
                            "field":"document.SUB_DOCUMENT_2.NAME_OF_YOUR_GEO_POINT_ATTRIBUTE",
                             "ranges": [{"to": 1000}, {"to": 3000, "from": 1000}, {"from": 3000}]
                             }
                }
        }}
}

Q: I want autocomplete?

A-0. NOTE better to use n-gramm based approach

A-1. Prefix approach for autocomplete:

{
    "query":{"query_string" : {
        "default_field" : "field.name",
        "query" : "start_of_phrase*"
    }},   
    "fields":["field.name"]
}

A-2. by adding to document mapping additional suggest field:

...
"mappings" : {
    "document_type": {
        "properties":{
             "suggest" : {
                        "type" : "completion",
                        "index_analyzer" :"simple",
                        "search_analyzer" :"simple",
                        "payloads":"true"
                    },
....

When you add document for indexing you have to specify this additional information and use special endpoint _suggest for request suggestions:

{
    "suggest_name" : {
        "text" : "k",
        "completion" : {
            "field" : "suggest"
        }
    }
}

Q: I want filtering of a search result by nested attribute!

{
  "query": {
    "filtered": {
      "query": {
        "match_all": {}
      },
      "filter": {
        "or": [
          {
            "nested": {
              "path": "document.nested_attribute",
              "filter": {
                "bool": {
                  "must": [
                    {
                      "terms": {
                        "document.nested_attribute.attribute_value": [
                          1,
                          2
                        ]
                      }
                    }
                  ]
                }
              }
            }
          },
          {
            "nested": {
              "path": "document.nested_attribute_1",
              "filter": {
                "bool": {
                  "must": [
                    {
                      "terms": {
                        "document.nested_attribute_1.attribute_value": [
                          "some string value"
                        ]
                      }
                    }
                  ]
                }
              }
            }
          }
        ]
      }
    }
  }
}

Heterogeneous vector in c++ – overview of common approaches

So, you are wondering about heterogeneous vector in c++?
Maybe even dare to dream about any suitable substitution of such non-existent container?
In another word, you need a generic-like container that can store different datatypes.

If you just need a quick answer – stick with std::vector < boost::any> approach or read this,
If you need more technical-rich overview of purely templated solution – scroll down to links part,
If you are wondering about other options and don’t mind to dive in a world of bad English grammar and details about one of my recent task – read on.

heterogeneous container in c++

So, you want a heterogeneous container in c++…

First ask yourself – do you really need a heterogeneous vector?
If your answer is – yes, I have a bad news for you – in 99.9 percent it’s just consequences of messy design.
However, I am sure you are here for the sake of that one exceptional case: for example – your task is providing intermediate peace of software for interaction with some 3rd party old-fashion engine.

In my case – I was trying to implement convenient way of operating variable length list of parameters for OpenCL kernel wrapper.

If you are not familiar with mechanism of interaction of OpenCL code with C++, there are only one problem (sarcasm!) – it is too verbose. Off course there are numerous third party wrappers – http://streamcomputing.eu/knowledge/for-developers/opencl-wrappers/ but in situation where even NVidia drivers sometimes do not support all features from those-before-the-last standard,
I am afraid to think about cases when you have to deal with additional layer of external api.
Yeah, lets think about your own implementation because development of your own bugs is very entertaining and educational. It’s time consuming as well as terrible error-prone but you can narrow desired functional for your needs and be sure that all issues are made by you.

OpenCL kernels are compiled independently of host code, so you do not have any standard approaches for checking whether arguments provided to kernel have appropriate types and whether their amount corresponds to definition of kernel. It means that:
1) In case you are too lazy to somehow analyze every OpenCL kernels you can’t check how many arguments is necessary for particular kernel
2) You can’t check whether provided arguments have proper data type without any external parser

As a consequence, in general, my wrapper should be able to deal with variable length array of arbitrary any-type parameters.

(NOTE: Yeah, I’m familiar with undocumented c++ wrappers based on variadic templates, but it force you to follow their low-level nature by falling down from level of domain-specific objects to operating in terms of POD types.)

From that brief idea, I conclude that my goal was:

vector < gpu_arg > kernel_args;

where gpu_arg is a class that can encapsulate any data types – built-in as well as a user-defined.
Who have mentioned templates? How to create vector that can hold any templated parameter? (we discuss it a bit latter)

I approach – return to the ancient times
The most straightforward way – forget about C++ and rely on encapsulation of data into void* pointers with numerous C-way casting:

struct gpu_arg
{
  void* data;
  size_t size;
  // numerous helper methods here
  // NOTE: you have to add some kind of type_id to deal with data in proper way
};

I.e. kernel parser report that there should be following parameter set:

float, int, custom_class *

and when you start adding parameters it treat them as predefined types (with or without your own additional datatypes checks).

As an advantage of such idea – we can easily use it in run-time.
In addition, this solution is error-prone and can lead to cruel punishment during any code review.

II approach – std::tuple and variadic templates
On the other hand – in many cases when you are not keen to find a perfect silver bullet you may find helpful to simplify task. In order to check argument’s types you have to preprocess kernel, so you can form an expected parameter list. If you perform this operation during compilation of host-side code, you may use acquired parameter list to simplify code-generation task.
I started investigation of possible approaches and find out that the most obvious solution would be based on std::tuple:

// this C++11 container allows creation custom container like this:
std::tuple < int, int, bool, float *, unsigned short * > parameters_set;

or encapsulate it in a class with some syntax sugar for convenience:

template < typename ...T >
class arguments_set
{

    std::tuple<T...> data;
    template< size_t I >
    using data_type = typename std::tuple_element<I, decltype(data)>::type;

    /*
     *      variadic-based routine for initialize every element of tuple
     * */
   	template < std::size_t I = 0, typename TT >
	void
	init ( TT & arg )
	{
        std::get<I>( data ) = arg;
	};

	template < std::size_t I = 0, typename TT, typename ...Args>
	void
	init ( TT & arg, Args ... args )
	{
		init <I,TT> ( arg );
		init <I+1,Args...>( args ... );
	};

public:

    template<typename... Ts>
    arguments_set(Ts... args) {
       init <0,Ts...> ( args... );
    };

    template < std::size_t I = 0>
    constexpr
    auto get ( ) -> data_type<I>
    {
        return std::get<I>(data);
    }

};

Argh templates, well, who care about compiler’s effort to parse all this fluff?
Despite of convenience of variadic templates constructor, template metaprogramming is not easy to deal with during maintenance phase (as well as during developing).
On the other hand, it provides a desired result – strong type-checking combined with ability to generate variable length list of parameters.

So, solution was:
1) run pre-processor for OpenCL kernels in order to generate proper tuple for method invocation
2) compile the whole module

It is can be a solution in situation where you are not intend to run this mechanism in run-time.
(because it mean you have to dynamically extend templated class tuple objects)
Not my case.
Idea of pre-compiled kernels (PTX) sound great, but reality is sad – mess of drivers, hardware and vendor’s ambitions lead to incompatibility of generated binaries in general case. Not usable for me :(.
(But hope springs eternal – if you are lucky enough you can play with CL_CONTEXT_OFFLINE_DEVICES_AMD, http://clusterchimps.org/ocltools.php, http://www.browndeertechnology.com/coprthr.htm )

III approach – type erasure

Ok, let’s return to my preconditions once again:
1) I need type checking – template?
2) I need it in run-time – maybe some virtual stuff?!

What if I declare interface of argument as an abstract class and inherit it as a templated child with proper data fields

i.e.:

// pure abstract class
// in case of necessity can be further divided on pure interface\data-fields parts

class gpu_arg_base {
  /*
   *  interface part that depend on child's template parameter = a lot of virtual functions
   */
  /*
   *  common data fields with ordinary setters\getters methods
   */
}

template < typename T>
class gpu_arg : gpu_arg_base {
  /*
   * explicit override of interface with possible overloading
   */
  gpu_arg ( T* init_data);
  private:
    T *data; // NOTE: just a reference to data, no allocation\de-allocation!
};

It allow me to use them in following way:

class kernel_wrapper {
    vector <gpu_array_base*> kernel_params;
     /* some stuff here */
    public:
        // variadic template functions to deal with any number of parameters
        template < typename T>
	void
	add_kernel_args ( T * arg )
	{
		add_kernel_arg ( arg );
	};

	template <typename T, typename ...Args>
	void
	add_kernel_args( T * arg, Args ... args )
	{
		add_kernel_arg ( arg );
		add_kernel_args ( args ... );
	};

        // generating of proper function for particular type
        template<class T>
        void add_kernel_arg( T * host_data )
        {
	        gpu_arg_base* new_arg = new gpu_arg<T> ( host_data );
		kernel_params.push_back( new_arg );
        };

     /* interface part */
}

But be careful with this easy-looking approach – there are two main issues which can affect your mood and calmness.
First, read about differences between overriding and hiding of methods in inheritance hierarchy here or here. It is a great source of confusion, especially during investigation of fresh bug-reports.
Second, do not forget about “covariant return type” rules – http://aycchen.wordpress.com/2009/08/17/covariant-return-type-in-cpp/.
Great article about possible caveats and workaround can be found there:
http://nerdland.net/2009/06/covariant-templatized-virtual-copy-constructors/

After reviewing all solutions described above, you may find that you accept additional dependency in exchange for absence of disastrous side-effects of your implementation.
boost::any or boost::variant can be a proper choice.

PS. Actually, I suspect that using tuples and dark magic of template metaprogramming, you can save few ticks of processor’s time by abandoning inheritance and virtual table, but as usual during development we have to balance between concept of the perfect code and requirements of too fussy world.

LINKS:

Example of heterogeneous container ( deeply nested approach)
www.codeproject.com/Articles/23304/High-Performance-Heterogeneous-Container

Interesting practical example of tuple usage for ORM-like engine:
http://javol.wordpress.com/2009/08/06/type-safe-table-container-using-variadic-templates/
Some practical aspects of using tuples:
http://stackoverflow.com/questions/1198260/iterate-over-tuple
http://stackoverflow.com/questions/15411022/how-do-i-replace-a-tuple-element-at-compile-time
http://stackoverflow.com/questions/7858817/unpacking-a-tuple-to-call-a-matching-function-pointer

Using variadic templates to initialize tuples or other way round:
http://stackoverflow.com/questions/10014713/build-tuple-using-variadic-templates
http://stackoverflow.com/questions/21413045/variadic-variable-initialization-for-variadic-template
http://stackoverflow.com/questions/687490/how-do-i-expand-a-tuple-into-variadic-template-functions-arguments

Any class in c++:
http://codereview.stackexchange.com/questions/20058/a-c11-any-class
www.codeproject.com/Articles/11250/High-Performance-Dynamic-Typing-in-C-using-a-Repla

Illustration of variadic templates usages for generating C++11 variant class:
http://thenewcpp.wordpress.com/2012/02/15/variadic-templates-part-3-or-how-i-wrote-a-variant-class/

Hands-on experience with tuples:
http://yapb-soc.blogspot.ru/2012/12/fun-with-tuples.html
http://yapb-soc.blogspot.ru/2012/12/zipping-and-mapping-tuples.html

How to convert png pair of RGB and Depth frames into Pointcloud library PCD format

There are a lot of accessible dataset of RGB-D data:

http://vision.in.tum.de/data/datasets/rgbd-dataset
http://rgbd-dataset.cs.washington.edu/dataset.html
http://research.microsoft.com/en-us/projects/7-scenes/
http://www0.cs.ucl.ac.uk/staff/M.Firman/RGBDdatasets/

But usually it stored in PNG format and unfortunately Pointcloud library do not provide built-in function neither for treating it as a PointCloud nor for conversion it to PCD. For my experiments I need to test few points using data with ground truth estimation, thats why I have to code small utility for conversion purpose.

Due to sudden leisure I decided to share that peace of code – probably you can find it useful.

https://github.com/kruglov-dmitry/pnd2pcd_batch

From readme:

png2pcd_batch – simple command line utility to convert depth and rgb frames
from png format to PCL pointcloud.

There are 2 execution mode:
using file with association information i.e. containing rgb-depth png files correspondence
or just providing folders that contain depth and rgb frames ( not reccommended ).

In 1st case you should anyhow create associate file by yourself
(for further details check description of parse_freiburg function)
In 2nd case – correspondence strictly depends on file names, and you should check it twice,
to avoid situation when selected depth frame is not appropriate for rgb frame.
( add sorting to filenames vector using custom predicate )

All dataset related parameters are incapsulated in Intr structure ( intrinsics ).
There are: width, height, fx, fy, cx, cy, scale_factor.
Usually depth data is saved as unsigned short ( 16 bit ),
but in pcl::PointXYZ you have to re-scale it to float – metric measurment.

Appropriate intrinsics should be written to file cam_params.cfg otherwise
default values will be used ( which may lead to invalid output data ).

There are exist two opportunity for compiling:

using classical make:
edit WORK_DIR in Makefile to point in directory contained pcl-trunk & opencv
make
it produce more lightweighted version by avoiding linkage with unnecessary libraries

or using cmake:

mkdir build; cd build
cmake ..
make

NOTE 1: There are only two dependencies:
PCL and OpenCV.
NOTE 2: in case of builded-but-not-properly-installed OpenCV libraries you have to
manually create symlink to ipp lib:
sudo ln -s /path-to-opencv/3rdparty/ippicv/unpack/ippicv_lnx/lib/intel64/libippicv.a /usr/lib/libippicv.a

Note 3: it have built-in support for 16bit unsigned depth and 3-channel RGB data only, in case your data has another format you have to change code a bit
Note 4: do not forget to provide appropriate intrinsics for proper calculation of XYZ vertex

Templates in plain C

Templates in ANSI C – simple and convenient method for emulating c++ like templates in plain c. Sample project, which demonstrate this technics can be found at github.

So, it is our constraints:

  • ANSI C (no templates, inheritance, overloading, default params etc.)
  • set of almost the same user-defined structures (the common difference – is types of internal fields)
  • set of the functions, which operates on user-defined structures and provide a common interface used in the whole app

The most straightforward way to solve such task is just hard coded all necessary routine by hand:

/*		first type - type_int							*/
typedef struct type_int {
	int data;
} type_int;

type_int
make_type_int(int init_val) {
	type_int return_value;
	return_value.data = init_val;
	return return_value;
}

type_int
subtract_type_int (type_int A, type_int B) {
	return make_type_int ( A.data - B.data );
}

/*
 *		and a lot of different functions here
 */

 /*		second type - type_float						*/
typedef struct type_float {
	float data;
} type_float;

/*
 *		etc.
 */

This leads to a huge amount of copy-paste and increase chances of errors, especially in case of a large set of functions and vicious habit of the compiler to use implicit type conversion.
But what is most important – such way a bit annoying and leads to impression of bad “smell” of your own code.
So I decided to google around (all helpful link are located at the end of articles) and find out that indeed – the better way for emulating templates in plain C is exist!

Here is my how-to for generating declaration of structures and implementation of methods operating on them, which can be used further in the whole project.
The main trick here is to refresh the basis of C preprocessor and macros.

Firstly, lets define several helpful macros in file my_types.h:

#define CAT(X,Y) X##_##Y
#define TYPE_NAME(X,Y) CAT(X,Y)

They will be used to generate names of your structures and methods using simple rule – merge two params, using underscore as delimiter.
Using macros above lets create our simple structure in file my_type_templates.h:

typedef struct TYPE_NAME(TYPE, SUB_TYPE) {
	SUB_TYPE data;
} TYPE_NAME(TYPE, SUB_TYPE);

And add declaration and implementation of all necessary functions:

#ifndef INCLUDED_IN_IMPLEMENTATION_FILE

/* if this file is included in any header - just add there definition of interface */
TYPE_NAME(TYPE, SUB_TYPE)
TYPE_NAME(make, TYPE_NAME(TYPE, SUB_TYPE) ) ( SUB_TYPE init_value);

TYPE_NAME(TYPE, SUB_TYPE)
TYPE_NAME(subtract, TYPE_NAME(TYPE, SUB_TYPE) ) ( TYPE_NAME(TYPE, SUB_TYPE) A, TYPE_NAME(TYPE, SUB_TYPE) B);

/*
 *		long list of supported functions
 */

#else

/* if this file is included in implementation file, where defined flag INCLUDED_IN_IMPLEMENTATION_FILE than generate implementaion of functions
 */

/*	add implementain make_* functions 		*/
TYPE_NAME(TYPE, SUB_TYPE)
TYPE_NAME(make, TYPE_NAME(TYPE, SUB_TYPE) ) ( SUB_TYPE init_value ) {
	TYPE_NAME(TYPE, SUB_TYPE) return_value;

	return_value.data = init_value;

	return return_value;
}

/*	add implementain subtract_* functions 		*/
TYPE_NAME(TYPE, SUB_TYPE)
TYPE_NAME(subtract, TYPE_NAME(TYPE, SUB_TYPE) ) ( TYPE_NAME(TYPE, SUB_TYPE) A, TYPE_NAME(TYPE, SUB_TYPE) B) {
	return TYPE_NAME(make, TYPE_NAME(TYPE, SUB_TYPE) ) ( A.data - B.data );
}

#endif

NOTE: you should not use any global ifdefs in file my_type_templates.h, because we have to include it multiple times, for every new custom type. Preprocessor will generate actual struct’s names and appropriate functions for manipulating them.

After that lets specify all types, which should be used in our project in usual header file my_types.h. For every type, which we want to generate – just add define/undef command like this:

#define TYPE type
#define SUB_TYPE int
    #include <my_type_templates.h>
#undef TYPE
#undef SUB_TYPE

and add implementation of all functions to a source file – my_types.c – just define flag showing that it is actual implementation and include header file, containing all defined types:

#define INCLUDED_IN_IMPLEMENTATION_FILE
#include <my_types.h>

In your project you should use my_types.h header as usual – just include it in all dependent sources. We have used ifdef for implementation part of our template, so header doesn’t contain any functions implementation – therefore there is no ambiguity during linking and all necessary function would be compile only once – during compilation of file my_types.c.

So the final files should looks like following:

my_types.h

#ifndef MY_TYPES
#define MY_TYPES

#define CAT(X,Y) X##_##Y
#define TYPE_NAME(X,Y) CAT(X,Y)

#define TYPE type

#define SUB_TYPE int
	#include <my_type_templates.h>
#undef SUB_TYPE

#define SUB_TYPE float
	#include <my_type_templates.h>
#undef SUB_TYPE

#undef TYPE

#endif /* MY_TYPES */

my_types.c

/*
 *		Add all includes necessary for you implementations
 */
#define INCLUDED_IN_IMPLEMENTATION_FILE
#include <my_types.h>

That’s it. Using this trick you will achieve compile-time type-checks, decrease amount of boring hand-coded routine and avoid possible errors using another approach, based on void pointers and multiple run-time casts.

Additional resources:
http://arnold.uthar.net/index.php?n=Work.TemplatesC
http://stackoverflow.com/questions/1489932/c-preprocessor-and-concatenation
http://stackoverflow.com/questions/351733/can-you-write-object-oriented-code-in-c

Что почитать для проф развития программисту

Давно хотел как-то упорядочить свой список книг для внеклассного чтения для повышения проф-пригодности. Эти книжки для тех программистов, которые уже не совсем новички. Возможно уже и не совсем программисты – техлиды/архитекты. И хотят данную ситуацию усугубить.
Я из них прочитал еще не все 🙁
Но галочки уже расставляю 🙂

зы. Не думаю, что это нужно/интересно/полезно вот прям всем – это уже лично мой список отражающий текущие или прошлые профессиональные интересы. Я ж наверняка что-то позабыл включить, а что-то мне разонравится и я буду безжалостно это вычеркивать – так что в статье ожидаются правки 🙂

C++

  1. Язык программирования С++, Страуструп
  2. Эффективное использование C++. 55 верных способов улучшить структуру и код ваших программ, Мейерс Скотт
  3. Наиболее эффективное использование С++. 35 новых рекомендаций по улучшению ваших программ и проектов, Мейерс Скотт
  4. C++: Библиотека программиста, Джефф Элджер
  5. Веревка достаточной длины, чтобы… выстрелить себе в ногу. Правила программирования на Си и Си++. Ален Голуб
  6. Стандарты программирования на С++. 101 правило и рекомедакция. Герб Саттер, Андрей Александреску
  7. C++. Практический подход к решению проблем программирования, Мэтью Уилсон
  8. Современное проектирование на С++: Обобщенное программирование и прикладные шаблоны проектирования, Андрей Александреску
  9. Advanced C++ Metaprogramming, Davide Di Gennaro
  10. Introduction to the Boost C++ Libraries, by Robert Demming

Алгоритмы

  1. Algorithms in a Nutshell, George T. Heineman, Gary Pollice, Stanley Selkow
  2. Алгоритмы на C++, Роберт Седжвик
  3. Алгоритмы. Построение и анализ, Томас Кормен
  4. Искусство программирования, Дональд Э. Кнут

Сети

  1. Эффективное программирование TCP-IP, Снейдер Й.
  2. UNIX. Разработка сетевых приложений,  У. Р. Стивенс

Функциональный подход к программированию

  1. Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp, Peter Norvig
  2. Learn You Some Erlang for Great Good!: A Beginner’s Guide, Fred Hebert
  3. ERLANG Programming, Francesco Cesarini, Simon Thompson
  4. Purely Functional Data Structures, Chris Okasaki
  5. Learn You a Haskell for Great Good!: A Beginner’s Guide, Miran Lipovaca

Проектирование ООП программ

  1. Head First Object-Oriented Analysis and Design, Brett D. McLaughlin, Gary Pollice, Dave West
  2. Head First Design Patterns, Elisabeth Freeman, Eric Freeman, Bert Bates, Kathy Sierra, Elisabeth Robson
  3. Head First Software Development, Dan Pilone, Russ Miles
  4. Domain-Driven Design: Tackling Complexity in the Heart of Software, Eric Evans
  5. An Introduction to Object-Oriented Analysis and Design and Iterative Development, Craig Larman

Компьютерное зрение

  1. Computer Vision: Models, Learning, and Inference, Simon J. D. Prince
  2. Multiple View Geometry in Computer Vision Richard Hartley, Andrew Zisserman
  3. Computer Vision: A Modern Approach, David A. Forsyth
  4. Компьютерное зрение, Шапиро, Стокман

ОБЩАЯ МЕТОДОЛОГИЯ ПРОГРАММИРОВАНИЯ

  1. Чистый код. Создание, анализ и рефакторинг, Роберт Мартин
  2. Совершенный код, Стив Макконнелл
  3. 97 этюдов для архитекторов программных систем, Нил Форд, Майкл Найгард, Билл де Ора
  4. Защищённый код, Майкл Ховард, Дэвид Леблан
  5. Рефакторинг. Улучшение существующего кода, Мартин Фаулер
  6. Шаблоны корпоративных приложений, Мартин Фаулер
  7. Enterprise Integration Patterns: Designing, Building, and Deploying Messaging Solutions, Bobby Woolf, Gregor Hohpe
  8. How to Design Programs: An Introduction to Programming and Computing, http://htdp.org/, Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, Shriram Krishnamurthi
  9. Structure and Interpretation of Computer Programs (SICP), http://mitpress.mit.edu/sicp, Harold Abelson, Gerald Jay Sussman, Julie Sussman
  10. The Pragmatic Programmer: From Journeyman to Master, Andrew Hunt
  11. Writing Solid Code, Steve Maguire
  12. Hacker’s Delight, Henry S. Warren
  13. The Software Architect’s Profession: An Introduction, Marc Sewel
  14. 19 смертных грехов, угрожающих безопасности программ, Ховард М., Лебланк Д., Виега Д.
  15. Компиляторы: принципы, технологии и инструменты, “книга дракона”, Альфреда В. Ахо, Рави Сети, Джеффри Д. Ульмана,
  16. Паттерны проектирования, Гамма, Хелм, Джонсон, Влиссидес
  17. Test Driven Development: By Example, Kent Beck
  18. Code Craft: The Practice of Writing Excellent Code, Pete Goodliffe
  19. The Art of Multiprocessor Programming, Maurice Herlihy
  20. The Architecture of Open Source Applications, Amy Brown, Greg Wilson

VIM (emacs – 😛)

  1. Practical Vim: Edit Text at the Speed of Thought, Drew Neil
  2. Learning the vi and Vim Editors, Arnold Robbins, Elbert Hannah, Linda Lamb

Project Managment

  1. Искусство войны, Сунь-Цзы
  2. Мифический человеко-месяц, или Как создаются программные системы, Фредерик Брукс
  3. The Psychology of Computer Programming, Gerald M. Weinberg
  4. Extreme Programming Explained, Kent Beck
  5. Agile Software Development: The Cooperative Game, Alistar Cockburn
  6. Peopleware: Productive Projects and Teams, Tom DeMarco
  7. Adaptive Software Development: A Collaborative Approach to Managing Complex Systems, James A. Highsmith
  8. Software Craftsmanship: The New Imperative, Pete McBreen
  9. Dynamics of Software Development, Jim McCarthy
  10. Antipatterns: Managing Software Organizations and People, Colin J. Neill, Philip A. Laplante, Joanna F. DeFranco
  11. AntiPatterns in Project Management, William J. Brown
  12. Beyond Chaos: The Expert Edge in Managing Software Development, Larry L. Constantine
  13. The Manager Pool: Patterns for Radical Leadership (Software Patterns Series), by Don Sherwood Olson
  14. Death March, Edward Yourdon
  15. Leading a Software Development Team: A developer’s guide to successfully leading people, Richard Whitehead
  16. Head First PMP, Jennifer Greene, Andrew Stellman
  17. Agile Software Development, Principles, Patterns, and Practices, Robert C. Martin
  18. Цель. Процесс непрерывного совершенствования, Элияху М. Голдрат, Джефф Кокс
  19. Как пасти котов. Наставление для программистов, руководящих другими программистами, Дж. Ханк Рейнвотер

UX design

  1. A Project Guide to UX Design: For user experience designers in the field or in the making (2nd Edition) (Voices That Matter), Russ Unger, Carolyn Chandler

и, на посошок

Некоторые любопытные обсуждения литературы для проф развития:

http://stackoverflow.com/questions/1711/what-is-the-single-most-influential-book-every-programmer-should-read
http://habrahabr.ru/post/135897/
http://mrelusive.com/books/books.html – список книг для разработчика игр

Что почитать начинающему программисту

В связи с тем, что периодически меня спрашивают – что почитать зеленому новичку, для становления на скользкий путь программирования – я решил вот прям тут назвать те книжки, по которым когда-то начинал сам.И которые до сих пор поминаю добрым словом.

Будет актуально для linux/windows системных и прикладных разработчиков. Если вы прочитаете и сможете пользоваться этим знанием – 85% процентов вакансий уровня middle (ну и junior) – ваши.

1st programming bookЯ тоже перфекционист. Но даже мне кажутся изрядно раздутыми общедоступные списки книг для начинающих программистов. Причем некоторые книги в этих списках, новичкам, по моему мнению, просто противопоказаны. Ну нельзя подавляющему большинству нормальных людей путь в с++ начинать со Страуструпа. Можно сколько угодно ломать копья, обсуждая фундаментальные труды Кнута, но такое чтиво, особенно если университетский курс вышки подзабыт, быстро вгоняет в уныние, навевая мысли о проф. непригодности. К таким суровым упражнением будет милосерднее подходить спустя пару лет разминки в боевых условиях. Когда по граблям проторены тропы и начинает формироваться опасная иллюзия, что мол который год уже программирую – чем это меня тут еще удивить можно? Computer science?! Не, не слышал.

Мне кажется – вредным вываливать на человека, только-только ступившего на нелегкую стезю программирования бесконечный листинг вообще всех значимых произведений от признанных мастодонтов жанра отразивших свой опыт, свой взгляд на индустрию и т.п. Да, будет здорово, если вы будете держать в уме такой список и потихоньку, ставить галочки по мере прочтения. Но уверения, что без всего этого в профессии нечего делать – кажутся мне излишне снобистскими.

Да, программирование это наука. Да, программирование – это математика (в явном или не очень виде). И всему этому учиться не переучиться. Но не все же сразу. А вот начинать я бы предложил в таком порядке:

Язык C – основа основ:

Язык программирования C - Керниган, Ритчи

Язык программирования C – Брайан Керниган, Деннис Ритчи
(C Programming Language by Brian W. Kernighan, Dennis M. Ritchie )

SQL – ну куда сейчас без баз данных:

SQL - запросы для простых смертных. Хернандес, Вьескас

SQL – запросы для простых смертных. Практическое руководство по манипулированию данными в SQL Майкл Дж. Хернандес, Джон Л. Вьескас
(SQL Queries for Mere Mortals: A Hands-On Guide to Data Manipulation in SQL by John L. Viescas, Michael J. Hernandez)

C++ – противоречивый, не простой и всемогущий 🙂

C++ за 21 день, Либерти

Джон Либерти Освой самостоятельно C++ за 21 день – прекрасная вводная книга в мир ужасных крестов
(Teach Yourself C++ in 21 Days – Jesse Liberty, Bradley L. Jones)

Линуксы – ОС кроме Windows?

Операционная система UNIX Робачевский, Немнюгин, Стесик

Операционная система UNIX Андрей Робачевский, Сергей Немнюгин, Ольга Стесик

Эту книжку уже можно пометить звездочкой – как не шибко простую для начинающих, но содержащую сокровенные знания о том как что работает в системе – как для администраторов так и для системных программистов – строение исполняемых файлов, чем отличается поток от процесса, IPC, примитивы синхронизации. А если этого будет мало: обратите внимание на

У. Ричард Стивенс, Стивен А. Раго: “UNIX. Профессиональное программирование”
Рихтер Джеффри “Windows для профессионалов: создание эффективных Win32-приложений с учетом специфики 64-разрядной версии Windows” (не смотря на то, что сейчас миром десктопных приложений правят C# и Java, именно в этих книгах детально изложена информация об особенностях программирования под конкретную ОС)

Функциональное программирование – это уже сильно опционально, для постепенной подготовки организма к просвещению и философскому подходу к программированию. (Они хоть и на английском зато с доходчивыми картинками и объяснениями концепций буквально “на пальцах”).

The Little Schemer - Daniel P. Friedman Matthias Felleisen

The Little Schemer – Daniel P. Friedman Matthias Felleisen

The Seasoned Schemer - Daniel P. Friedman Matthias Felleisen

The Seasoned Schemer – Daniel P. Friedman Matthias Felleisen

Land of Lisp, Conrad Barski

Land of Lisp: Learn to Program in Lisp, One Game at a Time! – Conrad Barski

GPU-оптимизация – прописные истины

Ядер много не бывает…

 

Современные GPU – это монструозные шустрые бестии, способные пережевывать гигабайты данных. Однако человек хитер и, как бы не росли вычислительные мощности, придумывает задачи все сложнее и сложнее, так что приходит момент когда с грустью приходиться констатировать – нужна оптимизацию 🙁

В данной статье описаны основные понятия, для того чтобы было легче ориентироваться в теории gpu-оптимизации и базовые правила, для того чтобы к этим понятиям, приходилось обращаться по-реже.

Причины по которой GPU эффективны для работы с большими объемами данных, требующих обработки:

  • у них большие возможности по параллельному исполнению задач (много-много процессоров)
  • высокая пропускная способность у памяти

Пропускная способность памяти (memory bandwidth) – это сколько информации – бит или гигабайт – может может быть передано за единицу времени секунду или процессорный такт.

Одна из задач оптимизации – задействовать по максимуму пропускную способность – увеличить показатели throughput (в идеале она должна быть равна memory bandwidth).

Для улучшения использования пропускной способности:

  • увеличить объем информации – использовать пропускной канал на полную (например каждый поток работает с флоат4)
  • уменьшать латентность – задержку между операциями

Задержка (latency) – промежуток времени между моментами, когда контролер запросил конкретную ячейку памяти и тем моментом, когда данные стали доступны процессору для выполнения инструкций. На саму задержку мы никак повлиять не можем – эти ограничения присутствуют на аппаратном уровне. Именно за счет этой задержки процессор может одновременно обслуживать несколько потоков – пока поток А запросил выделить ему памяти, поток Б может что-то посчитать, а поток С ждать пока к нему придут запрошенные данные.

Как снизить задержку (latency) если используется синхронизация:

  • уменьшить число потоков в блоке
  • увеличить число групп-блоков

Использование ресурсов GPU на полную – GPU Occupancy

В высоколобых разговорах об оптимизации часто мелькает термин – gpu occupancy или kernel occupancy – он отражает эффективность использования ресурсов-мощностей видеокарты. Отдельно отмечу – если вы даже и используете все ресурсы – это отнюдь не значит что вы используете их правильно.

Вычислительные мощности GPU – это сотни процессоров жадных до вычислений, при создании программы – ядра (kernel) – на плечи программиста ложиться бремя распределения нагрузки на них. Ошибка может привести к тому, что большая часть этих драгоценных ресурсов может бесцельно простаивать. Сейчас я объясню почему. Начать придется издалека.

Напомню, что варп (warp в терминологии NVidia, wavefront – в терминологии AMD) – набор потоков которые одновременно выполняют одну и туже функцию-кернел на процессоре. Потоки, объединенные программистом в блоки разбиваются на варпы планировщиком потоков (отдельно для каждого мультипроцессора) – пока один варп работает, второй ждет обработки запросов к памяти и т.д. Если какие-то из потоков варпа все еще выполняют вычисления, а другие уже сделали все что могли – имеет место быть неэффективное использование вычислительного ресурса – в народе именуемое простаивание мощностей.

Каждая точка синхронизации, каждое ветвление логики может породить такую ситуацию простоя.  Максимальная дивергенция (ветвление логики исполнения) зависит от размера варпа. Для GPU от NVidia – это 32, для AMD – 64.

Для того чтобы снизить простой мультипроцессора во время выполнения варпа:

  • минимизировать время ожидания барьеров
  • минимизировать расхождение логики выполнения в функции-кернеле

Для эффективного решения данной задачи имеет смысл разобраться – как же происходит формирование варпов (для случая с несколькими размерностями). На самом деле порядок простой – в первую очередь по X, потом по Y и, в последнюю очередь, Z.

ядро запускается с блоками размерностью 64x16, потоки разбиваются по варпам в порядке X, Y, Z - т.е. первые 64 элемента разбиваются на два варпа, потом вторые и т.д.

ядро запускается с блоками размерностью 64×16, потоки разбиваются по варпам в порядке X, Y, Z – т.е. первые 64 элемента разбиваются на два варпа, потом вторые и т.д.

Ядро запускается с блоками размерностью 16x64. В первый варп добавляются первые и вторые 16 элементов, во второй варп - третьи и четвертые и т.д.

Ядро запускается с блоками размерностью 16×64. В первый варп добавляются первые и вторые 16 элементов, во второй варп – третьи и четвертые и т.д.

более подробно про это можно почитать тут:
http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html#thread-hierarchy

Как снижать дивергенцию (помните – ветвление – не всегда причина критичной потери производительности)

  • когда у смежных потоков разные пути исполнения – много условий и переходов по ним – искать пути ре-структуризации
  • искать не сбалансированную загрузку потоков и решительно ее удалять (это когда у нас мало того что есть условия, дак еще из-за этих условиях первый поток всегда что-то вычисляет, а пятый в это условие не попадает и простаивает)

Как использовать ресурсы GPU по максимуму

Ресурсы GPU, к сожалению, тоже имеют свои ограничения. И, строго говоря, перед запуском функции-кернела имеет смысл определить лимиты и при распределении нагрузки эти лимиты учесть. Почему это важно?

У видеокарт есть ограничения на общее число потоков, которое может выполнять один мультипроцессор, максимальное число потоков в одном блоке, максимальное число варпов на одном процессоре, ограничения на различные виды памяти и т.п. Всю эту информацию можно запросить как программно, через соответствующее API так и предварительно с помощью утилит из SDK. (Модули deviceQuery для устройств NVidia, CLInfo – для видеокарт AMD).

Общая практика:

  • число блоков/рабочих групп потоков должно быть кратно количеству потоковых процессоров
  • размер блока/рабочей группы должен быть кратен размеру варпа

При этом следует учитывать что абсолютный минимум – 3-4 варпа/вейфронта крутятся одновременно на каждом процессоре, мудрые гайды советуют исходить из соображения – не меньше семи вейфронатов. При этом – не забывать ограничения по железу!

В голове все эти детали держать быстро надоедает, потому для расчет gpu-occupancy NVidia предложила неожиданный инструмент – эксельный(!) калькулятор набитый макросами. Туда можно ввести информацию по максимальному числу потоков для SM, число регистров и размер общей (shared) памяти доступных на потоковом процессоре, и используемые параметры запуска функций – а он выдает в процентах  эффективность использования ресурсов (и вы рвете на голове волосы осознавая что чтобы задействовать все ядра вам не хватает регистров).

сам калькулятор:
http://developer.download.nvidia.com/compute/cuda/CUDA_Occupancy_calculator.xls

информация по использованию:
http://docs.nvidia.com/cuda/cuda-c-best-practices-guide/#calculating-occupancy

GPU и операции с памятью

Видеокарты оптимизированы для 128-битных операций с памятью. Т.е. в идеале – каждая манипуляция с памятью, в идеале, должна изменять за раз 4 четырех-байтных значения. Основная неприятность для программиста заключается в том, что современные компиляторы для GPU не умеют оптимизировать такие вещи. Это приходится делать прямо в коде функции и, в среднем, приносит доли-процента по приросту производительности. Гораздо большее влияние на производительность имеет частота запросов к памяти.

Проблема обстоит в следующем – каждый запрос возвращает в ответ кусочек данных размером кратный 128 битам. А каждый поток использует лишь четверть его (в случае обычной четырех-байтовой переменной). Когда смежные потоки одновременно работают с данными расположенными последовательно в ячейках памяти – это снижает общее число обращений к памяти. Называется это явление – объединенные операции чтения и записи (coalesced access – good! both read and write) – и при верной организации кода (strided access to contiguous chunk of memory – bad!) может ощутимо улучшить производительность. При организации своего ядра – помните – смежный доступ – в пределах элементов одной строки памяти, работа с элементами столбца – это уже не так эффективно. Хотите больше деталей? мне понравилась вот эта pdf –  или гуглите на предмет “memory coalescing techniques“.

Лидирующие позиции в номинации “узкое место” занимает другая операция с памятью – копирование данных из памяти хоста в гпу. Копирование происходит не абы как, а из специально выделенной драйвером и системой области памяти: при запросе на копирование данных – система сначала копирует туда эти данные, а уже потом заливает их в GPU. Скорость транспортировки данных ограничена пропускной способностью шины PCI Express xN (где N число линий передачи данных) через которые современные видеокарты общаются с хостом.

Однако, лишнее копирование медленной памяти на хосте – это порою неоправданные издержки. Выход – использовать так называемую pinned memory – специальным образом помеченную область памяти, так что операционная система не имеет возможности выполнять с ней какие либо операции (например – выгрузить в свап/переместить по своему усмотрению и т.п.). Передача данных с хоста на видеокарту осуществляется без участия операционной системы – асинхронно, через DMA (direct memory access).

И, на последок, еще немного про память. Разделяемая память на мультипроцессоре обычно организована в виде банков памяти содержащих 32 битные слова – данные. Число банков по доброй традиции варьируется от одного поколения GPU к другому – 16/32 Если каждый поток обращается за данными в отдельный банк – все хорошо. Иначе получается несколько запросов на чтение/запись к одному банку и мы получаем – конфликт (shared memory bank conflict). Такие конфликтные обращения сериализуются и соответственно выполняются последовательно, а не параллельно. Если к одному банку обращаются все потоки – используется “широковещательный” ответ (broadcast) и конфликта нет. Существует несколько способов эффективно бороться с конфликтами доступа, мне понравилось описание основных методик по избавлению от конфликтов доступа к банкам памяти – тут.

Как сделать математические операции еще быстрее? Помнить что:

  • вычисления двойной точности – это высокая нагрузка операции с fp64 >> fp32
  • константы вида 3.13 в коде, по умолчанию, интерпретируется как fp64 если явно не указывать 3.14f
  • для оптимизации математики не лишним будет справиться в гайдах – а нет ли каких флажков у компилятора
  • производители включают в свои SDK функции, которые используют особенности устройств для достижения производительности (часто – в ущерб переносимости)

Для разработчиков CUDA имеет смысл обратить пристальное внимание на концепцию cuda stream,  позволяющих запускать сразу несколько функций-ядер на одному устройстве или совмещать асинхронное копирование данных с хоста на устройство во время выполнения функций. OpenCL, пока, такого функционала не предоставляет 🙁

Утиль для профилирования:

NVifia Visual Profiler
AMD CodeXL (бывший Amd APP Profiler)

Средства для дебугинга:
gDEBugger – http://www.gremedy.com/
CUDA-gdb – https://developer.nvidia.com/cuda-gdb

И отдельно хочу отметить функционал AMD APP KernelAnalyzer – статического анализатора кода (не требует наличия GPU в системе, умеет компилировать/разбирать собранные ядра для различных архитектур GPU от AMD). Сейчас входит в состав очередной системы для разработки все-в-одном – AMD CodeXL.
CUDA-MEMCHECK – анализатор от NVidia, призванный обеспечить функционал одноименного расширения для valgrind в мире CUDA-приложений.
http://multicore.doc.ic.ac.uk/tools/GPUVerify/ – интересная утилитка, анализирует ядра как CUDA так и OpenCL.

P. S. В качестве более пространного руководства по оптимизации, могу порекомендовать гуглить всевозможные best practices guide для OpenCL и CUDA.

Введение в GPU-вычисления – CUDA/OpenCL

Введение в GPU-вычисления

Видеокарты – это не только показатель фпс в новейших играх, это еще и первобытная мощь параллельных вычислений, оставляющая позади самые могучие процессоры. В видеокартах таится множество простых процессоров, умеющих лихо перемалывать большие объемы данных. GPU-программирование – это та отрасль параллельных вычислений где все еще никак не устаканятся единые стандарты – что затрудняет  использование простаивающих мощностей.

В этой заметке собрана информация которая поможет понять общие принципы GPU-программирования.

Введение в архитектуру GPU

Разделяют два вида устройств – то которое управляет общей логикой – host, и то которое умеет быстро выполнить некоторый набор инструкций над большим объемом данных – device.
Архитектура GPU

В роли хоста обычно выступает центральный процессор (CPU – например i5/i7).
В роли вычислительного устройства – видеокарта (GPU – GTX690/HD7970). Видеокарта содержит Compute Units – процессорные ядра. Неразбериху вводят и производители NVidia называет свои Streaming Multiprocessor unit или SMX , а
ATI – SIMD Engine или Vector Processor. В современных игровых видеокартах – их 8-32.
Процессорные ядра могут исполнять несколько потоков за счет того, что в каждом содержится несколько (8-16) потоковых процессоров (Stream Cores или Stream Processor). Для карт NVidia – вычисления производятся непосредственно на потоковых процессорах, но ATI ввели еще один уровень абстракции – каждый потоковый процессор, состоит из processing elementsPE (иногда называемых ALU – arithmetic and logic unit) – и вычисления происходят на них.

Необходимо явно подчеркнуть что конкретная архитектура (число всяческих процессоров) и вычислительные возможности варьируются от модели к модели – что несколько влияет на универсальность и простоту кода для видеокарт от обоих производителей.
Для CUDA-устройств от NVidia это sm10, sm20, sm30 и т.д. Для OpenCL видеокарт от ATI/NVidia определяющее значение имеет версия OpenCL реализованная в драйверах от производителя 1.0, 1.1, 1.2 и поддержка особенностей на уровне железа. Да, вы вполне можете столкнуться с ситуацией когда на уровне железа какие-то функции просто не реализованы (как например локальная память на амд-ешных видеокарт линейки HD4800). Да, вы вполне можете столкнуться с ситуацией когда какие-то функции не реализованы в драйверах (на момент написания – выполнение нескольких ядер на видео-картах от NVidia с помощью OpenCL).

Программирование для GPU

Выполнение программы на GPU

Программы пишутся на расширении языка Си от NVidia/OpenCL и компилируются с помощью специальных компиляторов входящих в SDK. У каждого производителя разумеется свой. Есть два варианта сборки – под целевую платформу – когда явно указывается на каком железе будет исполнятся код или в некоторый промежуточный код, который при запуске на целевом железе будет преобразован драйвером в набор конкретных инструкций для используемой архитектуры (с поправкой на вычислительные возможности железа).

Ядро - kernelВыполняемая на GPU программа называется ядром – kernel – что для CUDA что для OpenCL это и будет тот набор инструкций которые применяются ко всем данным. Функция одна, а данные на которых она выполняется – разные – принцип SIMD.

Важно понимать что память хоста (оперативная) и видеокарты – это две разные вещи и перед выполнением ядра на видеокарте, данные необходимо загрузить из оперативной памяти хоста в память видеокарты. Для того чтобы получить результат – необходимо выполнить обратный процесс. Здесь есть ограничения по скорости PCI-шины – потому чем реже данные будут гулять между видеокартой и хостом – тем лучше.

Драйвер CUDA/OpenCL разбивает входные данные на множество частей (потоки выполнения объединенные в блоки) и назначает для выполнения на каждый потоковый процессор. Программист может и должен указывать драйверу как максимально эффективно задействовать существующие вычислительные ресурсы, задавая размеры блоков и число потоков в них. Разумеется, максимально допустимые значения варьируются от устройства к устройству. Хорошая практика – перед выполнением запросить параметры железа, на котором будет выполняться ядро и на их основании вычислить оптимальные размеры блоков.

Схематично, распределение задач на GPU происходит так:

Выполнение программы на GPU

Выполнение программы на GPU

work-item (OpenCL)  или thread (CUDA) – ядро и набор данных, выполняется на Stream Processor (Processing Element в случае ATI устройств).
work group (OpenCL) или thread block (CUDA) выполняется на Multi Processor (SIMD Engine)
Grid (набор блоков такое понятие есть только у НВидиа) = выполняется на целом устройстве – GPU. Для выполнения на GPU все потоки объединяются в варпы (warp – CUDA) или вейффронты (wavefront – OpenCL) – пул потоков, назначенных на выполнение на одном отдельном мультипроцессоре. То есть если число блоков или рабочих групп оказалось больше чем число мултипроцессоров – фактически, в каждый момент времени выполняется группа (или группы) объединенные в варп – все остальные ожидают своей очереди.

Одно ядро может выполняться на нескольких GPU устройствах (как для CUDA так и для OpenCL, как для карточек ATI так и для NVidia).
Одно GPU-устройство может одновременно выполнять несколько ядер (как для CUDA так и для OpenCL, для NVidia – начиная с архитектуры 20 и выше). Ссылки по данным вопросам см. в конце статьи.

Модель памяти OpenCL (в скобках – терминология CUDA)

Модель памяти GPU

Здесь главное запомнить про время доступа к каждому виду памяти. Самый медленный это глобальная память – у современных видекарт ее аж до 6 Гб. Далее по скорости идет разделяемая память (shared – CUDA, local – OpenCL) – общая для всех потоков в блоке (thread block – CUDA, work-group – OpenCL) – однако ее всегда мало – 32-48 Кб для мультипроцессора. Самой быстрой является локальная память за счет использования регистров и кеширования, но надо понимать что все что не уместилось в кеши\регистры – будет хранится в глобальной памяти со всеми вытекающими.

Паттерны параллельного программирования для GPU

1. Map

Map - GPU parallel pattern

Map – GPU parallel pattern

Тут все просто – берем входной массив данных и к каждому элементу применяем некий оператор – ядро – никак не затрагивающий остальные элементы – т.е. читаем и пишем в определенные ячейки памяти.

Отношение – как один к одному (one-to-one).

out[i]=operator(int[i])

пример – перемножение матриц, оператор инкремента или декремента примененный к каждому элементу матрицы и т.п.

2. Scatter

Scatter - GPU parallel pattern

Scatter – GPU parallel pattern

Для каждого элемента входного массива мы вычисляем позицию в выходном массиве, на которое он окажет влияние (путем применения соответствующего оператора).

out[Loc[i]] = operator(in[i])

Отношение – как один ко многим (one-to-many).

3. Transpose

Transpose - GPU parallel pattern

Transpose – GPU parallel pattern

Данный паттерн можно рассматривать как частный случай паттерна scatter.
Используется для оптимизации вычислений – перераспределяя элементы в памяти можно достичь значительного повышения производительности.

4. Gather

Gather - GPU parallel pattern

Gather – GPU parallel pattern

Является обратным к паттерну Scatter – для каждого элемента в выходном массиве мы вычисляем индексы элементов из входного массива, которые окажут на него влияние:

out[i] = operator(in[Loc[i]])

Отношение – несколько к одному (many-to-one).

5. Stencil

Stencil - GPU parallel pattern

Stencil – GPU parallel pattern

Данный паттерн можно рассматривать как частный случай паттерна gather. Здесь для получения значения в каждой ячейке выходного массива используется определенный шаблон для вычисления всех элементов входного массива, которые повлияют на финальное значение. Всевозможные фильтры построены именно по этому принципу.

Отношение несколько к одному (several-to-one)

Пример:  фильтр  Гауссиана.

6. Reduce

Reduce - GPU parallel pattern

Reduce – GPU parallel pattern

Отношение все к одному (All-to-one)

Пример – вычисление суммы или максимума в массиве.

7. Scan/ Sort

При вычислении значения в каждой ячейке выходного массива необходимо учитывать значения каждого элемента входного. Существует две основные реализации – Hillis and Steele и Blelloch.

out[i] = F[i] = operator(F[i-1],in[i])

Отношение все ко всем (all-to-all).

Примеры – сортировка данных.

Полезные ссылки

Архитектура GPU – http://www.ixbt.com/video3/rad.shtml

Введение в CUDA:

http://cgm.computergraphics.ru/issues/issue16/cuda

Введение в OpenCL:

http://www.drdobbs.com/parallel/a-gentle-introduction-to-opencl/231002854

http://opencl.codeplex.com/wikipage?title=OpenCL%20Tutorials%20-%201

http://www.fixstars.com/en/opencl/book/OpenCLProgrammingBook/contents/

Хорошие статьи по основам программирования (отдельный интерес вызывает область применения):
http://www.mql5.com/ru/articles/405
http://www.mql5.com/ru/articles/407

Вебинары по OpenCL:

http://developer.amd.com/resources/heterogeneous-computing/opencl-zone/training-events/opencl-programming-webinar-series/

Курс на Udacity по программированию CUDA:

https://www.udacity.com/course/cs344

Выполнение ядра на нескольких GPU:

http://stackoverflow.com/questions/16478968/running-opencl-kernel-on-multiple-gpus
http://www.linkedin.com/groups/Any-new-ideas-on-using-139581.S.97270720
http://www.codeproject.com/Articles/167315/Part-4-Coordinating-Computations-with-OpenCL-Queue

Причем можно пойти по пути упрощения и задействовать один из специальных планировщиков:
http://www.ida.liu.se/~chrke/skepu/
http://aces.snu.ac.kr/Center_for_Manycore_Programming/SnuCL.html
http://runtime.bordeaux.inria.fr/StarPU/

Выполнение нескольких ядер одновременно на одном GPU:
http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html#conurrent-kernel-execution
http://stackoverflow.com/questions/12344223/cuda-understanding-concurrent-kernel-execution
http://stackoverflow.com/questions/9311015/cuda-concurrent-kernel-execution-with-multiple-kernels-per-stream
Для ATI карт упоминаний такой возможности я не нашел. В стандарте OpenCL есть флаг CL_QUEUE_OUT_OF_ORDER_EXEC_MODE_ENABLE но в настоящее время он поддерживается только для CPU.

Серия постов про паттерны параллельного программирования на сайте интела:
http://software.intel.com/en-us/blogs/2009/05/26/parallel-pattern-1-superscalar-sequences-and-task-graphs
http://software.intel.com/en-us/blogs/2009/06/03/parallel-pattern-2-speculative-selection
http://software.intel.com/en-us/blogs/2009/06/10/parallel-patterns-3-map
http://software.intel.com/en-us/blogs/2009/06/24/parallel-pattern-4-gather
http://software.intel.com/en-us/blogs/2009/07/07/parallel-pattern-5-stencils
http://software.intel.com/en-us/blogs/2009/07/14/parallel-pattern-6-partition
http://software.intel.com/en-us/blogs/2009/07/23/parallel-pattern-7-reduce
http://software.intel.com/en-us/blogs/2009/09/15/parallel-pattern-8-scan
http://software.intel.com/en-us/blogs/2009/12/01/parallel-pattern-9-pack
http://software.intel.com/en-us/blogs/2010/06/09/parallel-pattern-10-scatter

CUDA – grid, threads, blocks- раскладываем все по полочкам

http://stackoverflow.com/questions/2392250/understanding-cuda-grid-dimensions-block-dimensions-and-threads-organization-s
http://llpanorama.wordpress.com/2008/06/11/threads-and-blocks-and-grids-oh-my/

доступные в сети ресурсы по CUDA

http://nvlabs.github.io/moderngpu/
https://developer.nvidia.com/content/gpu-gems-part-i-natural-effects
https://developer.nvidia.com/content/gpu-gems-2
https://developer.nvidia.com/content/gpu-gems-3

UPDATE 28.06.2013

http://my-it-notes.com/2013/06/bases-of-gpu-optimisation/ – основы оптимизации программ для GPU

Враперы для взаимодействия с ОпенСЛ:
JOCL – Java bindings for OpenCL (JOCL)
PyOpenCL – для python
aparapi – полноценная библиотека для жавы

для хаскела
http://hackage.haskell.org/package/accelerate
http://hackage.haskell.org/package/hopencl

Интересные статью по OpenCL – тут.

доступные материалы курсов по параллельным вычислениям:

http://www.slac.stanford.edu/~rolfa/cudacourse/

http://www.cs.nyu.edu/courses/fall10/G22.2945-001/lectures.html

https://computing.llnl.gov/tutorials/parallel_comp/

UPDATE 23.11.2013
http://clcc.sourceforge.net/ – компилятор для OpenCL, удобен для проверки используемых в проекте OpenCL ядер. Поддерживает Windows, Mac. Хотя под Mac – для этих целей можно воспользоваться и “родным”, более продвинутым средством – openclc:

/System/Library/Frameworks/OpenCL.framework/Libraries/openclc -x cl -cl-std=CL1.1 -cl-auto-vectorize-enable -emit-gcl matrix_multiplication.cl

данная команда не только проверит ваш код на соответствие стандарту OpenCL, но, заодно, создаст и заготовки клиентского кода (в данном случае файлы matrix_multiplication.cl.h/matrix_multiplication.cl.cpp) для вызова ядра из пользовательского приложения.
https://github.com/petRUShka/vim-opencl – плагин для Vim’а с поддержкой проверки синтаксиса OpenCL

Практическое введение в компьютерное зрение

как научить компьютер читать

как научить компьютер читать

Компьютерное зрение?!

Итак, вы поддались веянию времени и задумали освоить компьютерное зрение. Спешу вас разочаровать – до вечера не управитесь. Однако, примерно представить себе что это вообще такое и с какой стороны подходить к изучению, пожалуй, сможете.

Компьютерное зрение (иногда его величают машинным) – это набор технологий и алгоритмов из уймы связанных и не очень областей объединенных одной целью – научить бездушный компьютер обозревать окружающую действительность с некоторой долей оразумения. Для того чтобы компьютер смог распознать на фотографии любимую бабушку Агафью Петровну, вам необходимо освоить всего навсего: методы машинного обучения, основы обработки изображений, принципы распараллеливания вычислений, немного математики – линейную алгебру, геометрия, дифуры и тервер (для верности можно добавить к списку оптику, физику и теорию обработки сигналов). Да, самое время опускать руки (и разминать голову).

На практике, вот это все разом необходимо далеко не всегда, так как зачастую небольшие упрощения позволяют махом отбросить большую часть сложностей (или добавить еще). Однако, для того чтобы осознанно использовать алгоритмы компьютерного зрения для конкретных практических задач – крайне желательно ориентироваться в плюсах-минусах методов и быть в курсе “state of the art” – последних исследований.

компьютерное зрение - сплав многих наук

компьютерное зрение – сплав многих наук

Эдакий массивный кус знаний не так-то просто переварить, а потому, в этой статье я попытался сгруппировать набор ссылок на всякие полезности для планомерного изучения темы. Данные заметки ни в коем случае на претендуют на всеобъемлемость представленной информации, однако могут послужить кратким справочником и отправной точкой для детального изучения, именно с точки зрения наискорейшего практического применения.

Вся информация разбита на несколько статей-лекций, где вся информация ужата на полтораста строк по каждой теме. Да, именно так будем давить на лень. Для того, чтобы вкратце обозначить основные принципы, актуальные сейчас методы компьютерного зрения и располезные ссылки – этого более чем достаточно. Желающим более фундаментальных и эпичных по объемам манускриптов – милости просим в конец данной статьи, в подраздел используемые материалы (в каждой статье ссылки тоже водятся в изобилии, но, как правило, они сугубо по упомянутой теме).

В качестве ободрения для тех, кому данная предметная область не очень близка – теория компьютерного зрения пестрит каким-то неимоверным числом специальных терминов из математики, которые очень эффективно отпугивают кажущимся уровнем сложности. Не принимайте близко к сердцу – страшные на слух слова оказываются элементарными для понимания.

Компьютерное зрение – практическое введение:

01 – изображение в компьютерном зрении
02 – (пред)обработка изображений
03 – features – локальные особенности – за что зацепиться взгляду
04 – поиск преобразования между особыми точками и немного моделирования
05 – машинное обучение для классификации изображений

Использованные материалы

Видео-лекции

на русском:
Видео-лекции спецкурсов ВМК МГУ “Введение в компьютерное зрение” и “Дополнительные главы компьютерного зрения”, за авторством Антона Конушина (Anton Konushin):
http://www.lektorium.tv/course/?id=22847 – первая часть на лекториуме.
http://www.youtube.com/playlist?list=PLbwKcm5vdiSYTm87ntDsYrksE4OfngSzY – все части на ютубе.
все прекрасно смотрится на удвоенной скорости.
http://moodle.graphicon.ru/course/view.php?id=4 – Вспомогательные материалы по курсам.
http://www.slideshare.net/ktoshik – презенташки к лекциям можно найти там.
UPDATE 23.11.2013
http://habrahabr.ru/company/yandex/blog/203136/– лекции Яндекса по компьютерному зрению
https://sites.google.com/site/cvnnsu/materialy-lekcij – материалы спец-курса “Компьютерное зрение” ННГУ им Н.И. Лобачевского

на английском:
Курс “Введения в компьютерное зрение” университета Флориды от профессора Dr. Mubarak Shahтынц. Ооочень разжевано.
Курс “Цифровая обработка изображений” Харагпурского университета (Индия) – детально и математично разжеваны основные методы низкоуровневой обработки – http://freevideolectures.com/Course/2316/Digital-Image-Processing-IIT-Kharagpur
Нейронные сети –
http://nptel.iitm.ac.in/video.php?subjectId=117105084
Математические основы компьютерного зрения на курсере от Prof. Malikтут.
Видео по использованию OpenCV для конкретных задач – http://www.youtube.com/user/18F4550videos

Литература:
Компьютерное зрение Шапиро, Стокман – основательная, относительно современная и единственная, мне известная, годная книга по данной теме на русском.

Фундаментальные труды, доступные для свободного скачивания:

http://szeliski.org/Book/Computer Vision: Algorithms and Applications – Richard Szeliski, Microsoft Research

http://www.computervisionmodels.com/Computer Vision: Models, Learning, and Inference Simon J.D. Prince

http://programmingcomputervision.com/Programming Computer Vision with Python by Jan Erik Solem

_Официально_, доступных для скачивания не видел, но тоже заслуживают внимания:
Digital Image Processing – Rafael C. Gonzalez Richard E. Woods
Computer Vision: A Modern Approach – Forsyth
Introduction to Machine Learning – Alpaydin

Библиотеки содержащие алгоритмы компьютерного зрения

http://opencv.org/ – первое, что приходит на ум в качестве общедоступного инструментария для погружения в предметную область. Часть алгоритмов перенесена на GPU. С учетом наличия готовых рецептов использования (книги на амазоне\в интернетах – Learning OpenCV, Mastering OpenCV) – идеальна для новичков.
http://www.vlfeat.org/ – алгоритмы компьютерного зрения на чистом C, есть интерфейсы для матлаба.
http://www.simplecv.org/ – библиотека на c/c++ построенная поверх OpenCV, основная цель проекта – предоставить упрощенный интерфейс ко всем алгоритмам. Есть готовое пособие для тех, кто совсем не в теме – “Practical Computer Vision with SimpleCV”.
http://intopii.com/ – большущий фреймворк на c++ для машинного обучения и анализа изображений, есть javacript’овый апи.
ViSP – c++ библиотека с алгоритмами компьютерного зрения (преимущественно в области отслеживания-треккинга и наблюдение)
SHARK – Machine learning library – C++ библиотека алгоритмов машинного обучения, выгодно отличается от альтернатив наличием больше нигде не реализованных алгоритмов
OpenVIDIA : Parallel GPU Computer Vision – алгоритмы компьютерного зрения на GPU (CUDA)
http://scikit-learn.org – методы машинного обучения на питоне
http://cs.unc.edu/~ccwu/siftgpu/ – имплементация алгоритма SIFT на gpu.
MATLAB (toolbox + sample) – наверное, самый простой (и затратный) способ попробовать алгоритмы компьютерного зрения:
http://www.mathworks.com/products/image/
http://www.mathworks.com/products/computer-vision/

Материалы по теме:

http://courses.graphicon.ru/ – учебные материалы (на русском) по курсам Обработки изображений и Компьютерного зрения
презентации по библиотеке OpenCV
Курс лекций по компьютерному зрению от курсеры – https://www.coursera.org/course/computervision (на момент публикации не активен)
Запись выступлений с конференции по компьютерному зрению 2012 года Франция

Материалы англоязычных курсов от ведущих вузов по компьютерному зрению:
CSE/EE486 Computer Vision I
CS395T: Visual Recognition
6.870 Grounding Object Recognition and Scene Understanding
(гуглить по этим названиям и искать полезные крупицы знания)
Washington CSE 576 (Graduate Computer Vision)
Trevor Darrell’s CS 280 Computer Vision class at Berkeley
Antonio Torralba’s 6.869 Advances in Computer Vision class at MIT
Michael Black’s CS 143 Introduction to Computer Vision class at Brown
Kristen Grauman’s CS 378 Computer Vision class at UT Austin
Alyosha Efros’ 15-463 Computational Photography
16-721 Learning-Based Methods in Vision classes at Carnegie Mellon
Pascal Fua’s CS-442 Introduction to Computer Vision class at EPFL

http://visionserver.lems.brown.edu/engn2910x/lectures.php – лекции в pdf формате

http://homepages.inf.ed.ac.uk/rbf/CVonline/ – структурированная и необъятная информация по компьютерному зрению

Библиографии по компьютерному зрению:
http://forums.udacity.com/questions/1033058/free-book-computer-vision-models-learning-and-inference
http://www.compvision.ru/wiki/
http://www.computervisiononline.com/books

http://www.cvpapers.com/rr.html – пространный список библиотек, с реализованными методами компьютерного зрения (computer vision algorithm implementation)
http://www.kernel-machines.org/software – список библиотек с алгоритмами машинного обучения, применимых для задач компьютерного зрения