Universality, primes and space communication

So, in mathematics we have the concept of universality in which we have laws like the law of large numbers, the Benford’s law (that I cited a lot in previous posts), the central limit theorem and many other laws that acts like laws of physics for the world of mathematics. These laws are not our inventions, I mean, the concepts are our inventions but the laws per se are universal, they are true no matter where you are on the earth or if you live far away on the universe. And that is why Frank Drake, one of the founders of SETI and also one of the pioneers in search for extraterrestrial intelligence came with this brilliant idea of using prime numbers (another example of universality) to communicate with distant worlds. The idea that Frank Drake had was the use of prime numbers to hide (not actually hide, but to make self evident, you’ll understand later) the dimension of a transmitted image in the image size itself.

So, imagine you are receiving a message that is a sequence of dashes and dots like “—.-.—.-.——–…-.—” that repeats after a short pause and then again and again. Let’s suppose that this message has the size of 1679 symbols. So you begin analyzing the number, which is in fact a semiprime number (the same used in cryptography, a number that is a product of two prime numbers) that can be factored in prime factors as 23*73=1679, and this is the only way to factor it in prime factors (actually all numbers have only a single set of prime factors that are unique, see Fundamental theorem of arithmetic). So, since there are only two prime factors, you will try to reshape the signal in a 2D image and this image can have the dimension of 23×73 or 73×23, when you arrange the image in one of these dimensions you’ll see that the image makes sense and the other will be just a random and strange sequence. By using prime numbers (or semiprimes) you just used the total image size to define the only two possible ways of arranging the image dimension.

Arecibo Radio Telescope

This idea was actually used in reality in 1974 by the Arecibo radio telescope when a message was broadcast in frequency modulation (FM) aiming the M13 globular star cluster at 25.000 light-years away:

M13 Globular Star Cluster

This message had the size (surprise) of 1679 binary digits and carried a lot of information of your world like: a graphical representation of an human, numbers from 1 to 10, a graphical representation of the Arecibo radio telescope, etc.

The message decoded as 23 rows and 73 columns is this:

Arecibo Message Shifted (Source: Wikipedia)

As you can see, the message looks a lot nonsensical, but when it is decoded as an image with 73 rows and 23 columns, it will show its real significance:

Arecibo Message with the correct dimension (Source: Wikipedia)

Amazing, don’t you think ? I hope you liked it !

- Christian S. Perone

 

The beauty of Bitcoin P2P network

So, in the last days I just released Protocoin, a framework in pure Python with a Bitcoin P2P network implementation. While I’m in process of development of the v.0.2 of the framework (with new and nice features like Bitcoin keys management – you can see some preview here) I would like to show a real-time visualization I’ve made with Protocoin and Ubigraph of a node connecting to a seed node and then issuing GetAddr message for each node and connecting on the received nodes in a breadth-first search fashion. I’ll release the code used to create this visualization in the next release of Protocoin as soon as possible. I hope you enjoy it !

Color legend

Yellow = Connecting
Green = Connected
Blue = Disconnected after connection

Video

Protocoin – a pure Python Bitcoin protocol implementation

Just release the first version of Protocoin, a pure Python Bitcoin protocol implementation, for more information see the documentation or the project in Github.

If you want to donate for the project, my Bitcoin address is: 1Q6JZEE5turJXaTn1fburWkqjhC4oMJ4yV.

I hope you like it !

- Christian S. Perone

Mapa de calor dos dados de acidentes de transito do DataPoa

Esta semana será disponibilzada a nova versão do Django GIS Brasil, segue abaixo um exemplo de mapa criado usando os novos dados do Django GIS Brasil importados do DataPoa.

O exemplo abaixo é um mapa de calor utilizando os dados de acidentes de trânsito em Porto Alegre /RS durante os anos de 2000 até 2012. Os eixos (ruas, avenidas, etc.) também estarão presentes no Django GIS Brasil.

 

Heatmap POA

Mapa de Acidentes de Trânsito em PoA/RS. Clique para ampliar.

Book Suggestion: Codex Seraphinianus

Today the Codex Seraphinianus just arrived (after months waiting in the pre-order state). I bought it from Amazon and I really recommend this edition for those who are interested because this is a very large edition with high quality textured paper and beautiful printing style. The book has also in the end a pocket with a small brochure called “Decodex” with a letter from Luigi Serafini.

The book is a very impressive creation by Luigi Serafini (or by the cat) dating from 1981 and presenting an impossible world that will cause to you the most strange feelings. See the photo of the cover and some pages below.

- Christian S. Perone

Codex Page

Codex Title

Machine Learning :: Cosine Similarity for Vector Space Models (Part III)

* It has been a long time since I wrote the TF-IDF tutorial (Part I and Part II) and as I promissed, here is the continuation of the tutorial. Unfortunately I had no time to fix the previous tutorials for the newer versions of the scikit-learn (sklearn) package nor to answer all the questions, but I hope to do that in a close future.

So, on the previous tutorials we learned how a document can be modeled in the Vector Space, how the TF-IDF transformation works and how the TF-IDF is calculated, now what we are going to learn is how to use a well-known similarity measure (Cosine Similarity) to calculate the similarity between different documents.

The Dot Product

Let’s begin with the definition of the dot product for two vectors: \vec{a} = (a_1, a_2, a_3, \ldots) and \vec{b} = (b_1, b_2, b_3, \ldots), where a_n and b_n are the components of the vector (features of the document, or TF-IDF values for each word of the document in our example) and the \mathit{n} is the dimension of the vectors:

  \vec{a} \cdot \vec{b} = \sum_{i=1}^n a_ib_i = a_1b_1 + a_2b_2 + \cdots + a_nb_n

As you can see, the definition of the dot product is a simple multiplication of each component from the both vectors added together. See an example of a dot product for two vectors with 2 dimensions each (2D):

  \vec{a} = (0, 3) \\   \vec{b} = (4, 0) \\   \vec{a} \cdot \vec{b} = 0*4 + 3*0 = 0

The first thing you probably noticed is that the result of a dot product between two vectors isn’t another vector but a single value, a scalar.

This is all very simple and easy to understand, but what is a dot product ? What is the intuitive idea behind it ? What does it mean to have a dot product of zero ? To understand it, we need to understand what is the geometric definition of the dot product:

  \vec{a} \cdot \vec{b} = \|\vec{a}\|\|\vec{b}\|\cos{\theta}

Rearranging the equation to understand it better using the commutative property, we have:

   \vec{a} \cdot \vec{b} = \|\vec{b}\|\|\vec{a}\|\cos{\theta}

So, what is the term \displaystyle \|\vec{a}\|\cos{\theta} ? This term is the projection of the vector \vec{a} into the vector \vec{b} as shown on the image below:

The projection of the vector A into the vector B. By Wikipedia.

Now, what happens when the vector \vec{a} is orthogonal (with an angle of 90 degrees) to the vector \vec{b} like on the image below ?

Two orthogonal vectors (with 90 degrees angle).

There will be no adjacent side on the triangle, it will be equivalent to zero, the term \displaystyle \|\vec{a}\|\cos{\theta} will be zero and the resulting multiplication with the magnitude of the vector \vec{b} will also be zero. Now you know that, when the dot product between two different vectors is zero, they are orthogonal to each other (they have an angle of 90 degrees), this is a very neat way to check the orthogonality of different vectors. It is also important to note that we are using 2D examples, but the most amazing fact about it is that we can also calculate angles and similarity between vectors in higher dimensional spaces, and that is why math let us see far than the obvious even when we can’t visualize or imagine what is the angle between two vectors with twelve dimensions for instance.

The Cosine Similarity

The cosine similarity between two vectors (or two documents on the Vector Space) is a measure that calculates the cosine of the angle between them. This metric is a measurement of orientation and not magnitude, it can be seen as a comparison between documents on a normalized space because we’re not taking into the consideration only the magnitude of each word count (tf-idf) of each document, but the angle between the documents. What we have to do to build the cosine similarity equation is to solve the equation of the dot product for the \cos{\theta}:

   \displaystyle   \vec{a} \cdot \vec{b} = \|\vec{a}\|\|\vec{b}\|\cos{\theta} \\   \cos{\theta} = \frac{\vec{a} \cdot \vec{b}}{\|\vec{a}\|\|\vec{b}\|}

And that is it, this is the cosine similarity formula. Cosine Similarity will generate a metric that says how related are two documents by looking at the angle instead of magnitude, like in the examples below:

The Cosine Similarity values for different documents, 1 (same direction), 0 (90 deg.), -1 (opposite directions).

Note that even if we had a vector pointing to a point far from another vector, they still could have an small angle and that is the central point on the use of Cosine Similarity, the measurement tends to ignore the higher term count on documents. Suppose we have a document with the word “sky” appearing 200 times and another document with the word “sky” appearing 50, the Euclidean distance between them will be higher but the angle will still be small because they are pointing to the same direction, which is what matters when we are comparing documents.

Now that we have a Vector Space Model of documents (like on the image below) modeled as vectors (with TF-IDF counts) and also have a formula to calculate the similarity between different documents in this space, let’s see now how we do it in practice using scikit-learn (sklearn).

Vector Space Model

Practice Using Scikit-learn (sklearn)

* In this tutorial I’m using the Python 2.7.5 and Scikit-learn 0.14.1.

The first thing we need to do is to define our set of example documents:

1
2
3
4
5
6
documents = (
"The sky is blue",
"The sun is bright",
"The sun in the sky is bright",
"We can see the shining sun, the bright sun"
)

And then we instantiate the Sklearn TF-IDF Vectorizer and transform our documents into the TF-IDF matrix:

1
2
3
4
5
from sklearn.feature_extraction.text import TfidfVectorizer
tfidf_vectorizer = TfidfVectorizer()
tfidf_matrix = tfidf_vectorizer.fit_transform(documents)
print tfidf_matrix.shape
(4, 11)

Now we have the TF-IDF matrix (tfidf_matrix) for each document (the number of rows of the matrix) with 11 tf-idf terms (the number of columns from the matrix), we can calculate the Cosine Similarity between the first document (“The sky is blue”) with each of the other documents of the set:

1
2
3
from sklearn.metrics.pairwise import cosine_similarity
cosine_similarity(tfidf_matrix[0:1], tfidf_matrix)
array([[ 1.        ,  0.36651513,  0.52305744,  0.13448867]])

The tfidf_matrix[0:1] is the Scipy operation to get the first row of the sparse matrix and the resulting array is the Cosine Similarity between the first document with all documents in the set. Note that the first value of the array is 1.0 because it is the Cosine Similarity between the first document with itself. Also note that due to the presence of similar words on the third document (“The sun in the sky is bright”), it achieved a better score.

If you want, you can also solve the Cosine Similarity for the angle between vectors:

   \cos{\theta} = \frac{\vec{a} \cdot \vec{b}}{\|\vec{a}\|\|\vec{b}\|}

We only need to isolate the angle (\theta) and move the \cos to the right hand of the equation:

   \theta = \arccos{\frac{\vec{a} \cdot \vec{b}}{\|\vec{a}\|\|\vec{b}\|}}

The \arccos is the same as the inverse of the cosine (\cos^-1).

 Lets for instance, check the angle between the first and third documents:
1
2
3
4
5
6
import math
# This was already calculated on the previous step, so we just use the value
cos_sim = 0.52305744
angle_in_radians = math.acos(cos_sim)
print math.degrees(angle_in_radians)
58.462437107432784
 And that angle of ~58.5 is the angle between the first and the third document of our document set.
That is it, I hope you liked this third tutorial !

Related Material

A video about Dot Product on The Khan Academy

Wikipedia: Dot Product

Wikipedia: Cosine Similarity

Scikit-learn (sklearn) – The de facto Machine Learning package for Python

Rastreamento em tempo real de avioes em Porto Alegre utilizando Raspberry Pi + Radio UHF (SDR RTL2832U)

* This post is in Portuguese.

SDR (Software-Defined Radio)

SDR é uma área de radiocomunicação baseada em uma ideia muito simples: implementar em software o que antes era implementado em hardware (ex: mod/demod, filtros, etc). O fato do SDR estar se tornando uma tendência hoje se dá principalmente pelo baixo custo de alguns receptores como por exemplo o RTL2832U (mais sobre ele depois) que hoje você pode encontrar facilmente por uns U$ 20.00, preço este muito barato se você levar em consideração o intervalo de cobertura das frequências de 22Mhz até 2200Mhz (dependendo do tuner). Neste intervalo dá pra se ter uma ampla cobertura de sinais de rádio AM/FM, rádio da polícia, TV, GSM, GPS, ADSB (este post é sobre o ADSB), comunicação marítma, LTE (ainda em definição no Brasil) e outras aplicações que estão inseridas neste intervalo de frequência.

Um sistema SDR é composto geralmente por: um receptor ligado ao computador ou qualquer outro dispositivo embarcado com um poder de processamento razoável (por meio de placa de captura de áudio, USB, etc) e um software que irá fazer o tratamento do sinal recebido. Neste post eu vou utilizar o Raspberry Pi como dispositivo embarcado para capturar e demodular os dados enviados pelos transponders presentes em aeronaves comerciais e domésticas.

ADS-B (Automatic dependent surveillance-broadcast)

Grande parte dos aviões modernos estão sendo equipados com um dispositivo que tem o objetivo de substituir os radares que existem hoje. Até o ano de 2020 todos os aviões que entrarem no espaço aéreo estadunidense deverão ter como item obrigatório um dispositivo compatível com ADS-B. O dispositivo ADS-B faz com que as aeronaves sejam visíveis aos radares em terra e também para outros aviões através do broadcast de mensagens com sua altura, velocidade, posição e muitas outras informações relevantes. A transmissão destas mensagens se dá através da frequência 1090Mhz, uma frequência dentro do intervalo de captura de maioria dos receptores SDR usando o chipset RTL2832U. A ideia deste post é usar o Raspberry Pi para receber este broadcast enviado diretamente pelo transponder dos aviões, demodular os frames e então utilizar um software para decodificar/interpretar os frames e plotar em um mapa a posição atual dos aviões em Porto Alegre / RS.

Realtek RTL2832U


Alguns receptores de TV digital USB utilizam o chipset da Realtek RTL2832U, como este meu acima. Em 2012 foi descoberto que este chipset permitia o envio de dados brutos do receptor para o host, permitindo assim seu uso para SDR. Existem alguns projetos com drivers para se comunicar com o dispositivo e receber estes dados (Linux e Windows), entre os quais o mais utilizado em Linux é o projeto rtl-sdr, que agrega além do driver alguns utilitários de linha de comando como por exemplo o “rtl_adsb” que utilizarei no Raspberry Pi para demodular o sinal ADS-B enviado pelas aeronaves; outro componente importante nos receptores USB é o tuner, que é responsável pelo ajuste da frequencia do rádio, no caso do meu dongle USB ele é o R820T que tem uma ótima sensibilidade mas tem um intervalo menor de cobertura do espectro quando comparado ao E4000 (da Elonics), veja a tabela no site do projeto para saber o intervalo de cobertura de cada tuner e de outros hardwares suportados pelo rtl-sdr.

Compilando o rtl-sdr no Raspberry Pi

Estou utilizando o Raspberry Pi como host do dongle USB porque ele é um aparelho barato e o consumo de energia é muito baixo, ou seja, você pode deixá-lo ligado capturando o sinal ADS-B por quanto tempo quiser sem se preocupar com um gasto maior que 5 watts no pior caso.

Baixando repositório

1
git clone git://git.osmocom.org/rtl-sdr.git

Dependências: libusb-1.0-0-dev, cmake, compilador (gcc)

 Criando arquivos para compilação e compilando:
1
2
3
4
5
6
7
cd rtl-sdr/
mkdir build
cd build
cmake ../
make
sudo make install
sudo ldconfig
E pronto, já estamos com o rtl-sdr instalado (driver a aplicativos extras).

Recebendo sinal ADS-B

Antes de mais nada, um pequeno teste para verificar se o rtl-sdr está encontrando corretamente o dongle USB:

1
2
3
4
5
6
7
8
9
10
11
pi@raspberrypi ~ $ rtl_test -t
Found 1 device(s):
 0: ezcap USB 2.0 DVB-T/DAB/FM dongle</pre>
<pre>Using device 0: ezcap USB 2.0 DVB-T/DAB/FM dongle
Found Rafael Micro R820T tuner
Supported gain values (29): 0.0 0.9 1.4 2.7 3.7 7.7
8.7 12.5 14.4 15.7 16.6 19.7 20.7 22.9 25.4 28.0
29.7 32.8 33.8 36.4 37.2 38.6 40.2 42.1 43.4 43.9
44.5 48.0 49.6
No E4000 tuner found, aborting.
pi@raspberrypi ~ $

Note que o meu dongle é um RTL2832U com o tuner R820T, ao executar o “rtl_test -t” é também exibida uma lista com os ganhos suportados pelo dongle.

Como a frequência utilizada pelo ADS-B é de 1090MHz, uma antena boa seria uma discone ou uma dipolo confeccionada com as dimensões corretas para esta frequência. Como ainda não tenho os plugs adequados tive que utiliar a antena que veio junto com o dongle, que mesmo sendo de baixa qualidade e não relacionada com a frequência do ADS-B ainda consegue receber os sinais (de fato, mesmo desconectando a antena eu consigo receber os frames das aeronaves), mesmo com o dongle em um ambiente fechado (minha casa fica há uns 6-10km do aeroporto de Porto Alegre / RS).

Para receber e demodular os frames eu utilizei o utilitário “rtl_adsb” (ele vem junto com o pacote do rtl-sdr). Ao ser executado, ele ajustará o tuner para a frequência do transponder das aeronaves em 1090MHz e logo após fará a demodulação dos frames para o formato hexadecimal:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
pi@raspberrypi ~ $ rtl_adsb
Found 1 device(s):
  0:  Realtek, RTL2838UHIDIR, SN: 00000013

Using device 0: ezcap USB 2.0 DVB-T/DAB/FM dongle
Found Rafael Micro R820T tuner
Tuner gain set to automatic.
Tuned to 1090000000 Hz.
Sampling at 2000000 Hz.
Exact sample rate is: 2000000.052982 Hz
*825566cf477b3124c64b17e74b15;
*e6c7d7fdb34c855db6972204ea14;
*d1e27bb95df2454ca547c87718a2;
*906bc5a59b5c5053226fb94f3460;
*a6f51dc76353efeeabfbfe6946cb;
*e78ed3aaf547fcd87e8e4f41cea3;
*d26a5ecacdb7051f2ebe18efc613;

Cada frame inicia sempre com um asterisco na frente e cada um destes frames foi enviado diretamente por um transponder de um avião ou é uma requisição terra->ar de alguma base em terra. O que precisamos agora é fazer a decodificação destes frames para poder extrair o tipo do frame, latitude, longitude, callsign, origem e destino do avião, etc. Não existem hoje muitas alternativas open-source para fazer o plot dos aviões em um mapa, o melhor que eu encontrei foi o Virtual Radar Server que é open-source e roda também em Linux, além de ter uma interface web bem amigável e plotar as aeronaves usando o Google Maps.
Para fazer com que o Virtual Radar Server conecte no Raspberry Pi, primeiramente precisamos fazer o streaming via TCP dos frames que o “rtl_adsb” está recebendo no Raspberry Pi, o que dá para resolver utilizando o “netcat” mesmo:

1
rtl_adsb | netcat -lp 8080

Neste caso ele irá escutar na porta 8080 e enviar os frames ADS-B para o cliente que conectar nele. Logo após é só especificar o IP/porta do Raspberry Pi no Virtual Radar Server e se tudo der certo e você conseguir receber algum frame de algum transponder, você verá uma tela parecida com esta mostrada abaixo com o rastreamento dos aviões em tempo real:

No screenshot você pode ver um avião da GOL (GOL1446) se dirigindo ao aeroporto (logo a frente onde diz São João) a uma velocidade de 250km/h e descendo a uma velocidade de 195 metros por minuto. Geralmente os aviões enviam o broadcast da mensagem com a posição a cada segundo, tudo vai depender da sua antena, receptor e condições de difusão. Com a minha antena pequena e no meio de prédios eu consegui capturar o broadcast de aviõe em até uns 80km de distância, espero melhorar isto com uma outra antena, só preciso achar o material agora =)

- Christian S. Perone

Raspberry Pi & Arduino: a laser pointer communication and a LDR voltage sigmoid

So I finally got some more time to play with my Raspberry Pi GPIOs and Arduino, this post will explain how to use a LDR (Photoresistor, Light Dependent Resistor) on the Raspberry Pi to detect a laser light emitted by an Arduino.

Read more…

Genetic Programming and a LLVM JIT for restricted Python AST expressions

A small intro on the rationale

So I’m working on a Symbolic Regression Machine written in C/C++ called Shine, which is intended to be a JIT for Genetic Programming libraries (like Pyevolve for instance). The main rationale behind Shine is that we have today a lot of research on speeding Genetic Programming using GPUs (the GPU fever !) or any other special hardware, etc, however we don’t have many papers talking about optimizing GP using the state of art compilers optimizations like we have on clang, gcc, etc.

The “hot spot” or the component that consumes a lot of CPU resources today on Genetic Programming is the evaluation of each individual in order to calculate the fitness of the program tree. This evaluation is often executed on each set of parameters of the “training” set. Suppose you want to make a symbolic regression of a single expression like the Pythagoras Theorem and you have a linear space of parameters from 1.0 to 1000.0 with a step of 0.1 you have 10.000 evaluations for each individual (program tree) of your population !

What Shine does is described on the image below:

It takes the individual of the Genetic Programming engine and then converts it to LLVM Intermediate Representation (LLVM assembly language), after that it runs the transformation passes of the LLVM (here is where the true power of modern compilers enter on the GP context) and then the LLVM JIT converts the optimized LLVM IR into native code for the specified target (X86, PowerPC, etc).

You can see below the Shine architecture:

This architecture brings a lot of flexibility for Genetic Programming, you can for instance write functions that could be used later on your individuals on any language supported by the LLVM, what matters to Shine is the LLVM IR, you can use any language that LLVM supports and then use the IR generated by LLVM, you can mix code from C, C++, Ada, Fortran, D, etc and use your functions as non-terminal nodes of your Genetic Programming trees.

Shine is still on its earlier development, it looks a simple idea but I still have a lot of problems to solve, things like how to JIT the evaluation process itself instead of doing calls from Python using ctypes bindings of the JITed trees.

Doing Genetic Programming on the Python AST itself

During the development of Shine, an idea happened to me, that I could use a restricted Python Abstract Syntax Tree (AST) as the representation of individuals on a Genetic Programming engine, the main advantage of this is the flexibility and the possibility to reuse a lot of things. Of course that a shared library written in C/C++ would be useful for a lot of Genetic Programming engines that doesn’t uses Python, but since my spare time to work on this is becoming more and more rare I started to rethink the approach and use Python and the LLVM bindings for LLVM (LLVMPY) and I just discovered that is pretty easy to JIT a restricted set of the Python AST to native code using LLVM, and this is what this post is going to show.

JIT’ing a restricted Python AST

The most amazing part of LLVM is obviously the amount of transformation passes, the JIT and of course the ability to use the entire framework through a simple API (ok, not so simple sometimes). To simplify this example, I’m going to use an arbitrary restricted AST set of the Python AST that supports only subtraction (-), addition (+), multiplication (*) and division (/).

To understand the Python AST, you can use the Python parser that converts source into AST:

1
2
3
4
5
6
7
8
9
10
>>> import ast
>>> astp = ast.parse("2*7")
>>> ast.dump(astp)
'Module(
    body=[Expr(
        value=BinOp(
            left=Num(n=2), op=Mult(), right=Num(n=7)
        )
    )]
)'

What the parse created was an Abstract Syntax Tree containing the BinOp (Binary Operation) with the left operator as the number 2, the right operator as the number 7 and the operation itself as Multiplication(Mult), very easy to understand. What we are going to do to create the LLVM IR is to create a visitor that is going to visit each node of the tree. To do that, we can subclass the Python NodeVisitor class from the ast module. What the NodeVisitor does is to visit each node of the tree and then call the method ‘visit_OPERATOR’ if it exists, when the NodeVisitor is going to visit the node for the BinOp for example, it will call the method ‘visit_BinOp’ passing as parameter the BinOp node itself.

The structure of the class for for the JIT visitor will look like the code below:

1
2
3
4
5
6
7
8
9
10
# Import the ast and the llvm Python bindings
import ast
from llvm import *
from llvm.core import *
from llvm.ee import *
import llvm.passes as lp

class AstJit(ast.NodeVisitor):
    def __init__(self):
        pass

What we need to do now is to create an initialization method to keep the last state of the JIT visitor, this is needed because we are going to JIT the content of the Python AST into a function and the last instruction of the function needs to return what was the result of the last instruction visited by the JIT. We also need to receive a LLVM Module object in which our function will be created as well the closure type, for the sake of simplicity I’m not type any object, I’m just assuming that all numbers from the expression are integers, so the closure type will be the LLVM integer type.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
    def __init__(self, module, parameters):
        self.last_state = None
        self.module = module
        # Parameters that will be created on the IR function
        self.parameters = parameters
        self.closure_type = Type.int()
        # An attribute to hold a link to the created function
        # so we can use it to JIT later
        self.func_obj = None
        self._create_builder()

    def _create_builder(self):
        # How many parameters of integer type
        params = [self.closure_type] * len(self.parameters)

        # The prototype of the function, returning a integer
        # and receiving the integer parameters
        ty_func = Type.function(self.closure_type, params)

        # Add the function to the module with the name 'func_ast_jit'
        self.func_obj = self.module.add_function(ty_func, 'func_ast_jit')

        # Create an argument in the function for each parameter specified
        for index, pname in enumerate(self.parameters):
            self.func_obj.args[index].name = pname

        # Create a basic block and the builder
        bb = self.func_obj.append_basic_block("entry")
        self.builder = Builder.new(bb)

Now what we need to implement on our visitor is the ‘visit_OPERATOR’ methods for the BinOp and for the Numand Name operators. We will also implement the method to create the return instruction that will return the last state.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
    # A 'Name' is a node produced in the AST when you
    # access a variable, like '2+x+y', 'x' and 'y' are
    # the two names created on the AST for the expression.
    def visit_Name(self, node):
        # This variable is what function argument ?
        index = self.parameters.index(node.id)
        self.last_state = self.func_obj.args[index]
        return self.last_state

    # Here we create a LLVM IR integer constant using the
    # Num node, on the expression '2+3' you'll have two
    # Num nodes, the Num(n=2) and the Num(n=3).
    def visit_Num(self, node):
        self.last_state = Constant.int(self.closure_type, node.n)
        return self.last_state
 
    # The visitor for the binary operation
    def visit_BinOp(self, node):
        # Get the operation, left and right arguments
        lhs = self.visit(node.left)
        rhs = self.visit(node.right)
        op = node.op

        # Convert each operation (Sub, Add, Mult, Div) to their
        # LLVM IR integer instruction equivalent
        if isinstance(op, ast.Sub):
            op = self.builder.sub(lhs, rhs, 'sub_t')
        elif isinstance(op, ast.Add):
            op = self.builder.add(lhs, rhs, 'add_t')
        elif isinstance(op, ast.Mult):
            op = self.builder.mul(lhs, rhs, 'mul_t')
        elif isinstance(op, ast.Div):
            op = self.builder.sdiv(lhs, rhs, 'sdiv_t')
       
        self.last_state = op
        return self.last_state

    # Build the return (ret) statement with the last state
    def build_return(self):
        self.builder.ret(self.last_state)

And that is it, our visitor is ready to convert a Python AST to a LLVM IR assembly language, to run it we’ll first create a LLVM module and an expression:

1
2
3
4
5
module = Module.new('ast_jit_module')
# Note that I'm using two variables 'a' and 'b'
expr = "(2+3*b+33*(10/2)+1+3/3+a)/2"
node = ast.parse(expr)
print ast.dump(node)

Will output:

Module(body=[Expr(value=BinOp(left=BinOp(left=BinOp(left=BinOp(
left=BinOp(left=BinOp(left=Num(n=2), op=Add(), right=BinOp(
left=Num(n=3), op=Mult(), right=Name(id='b', ctx=Load()))), op=Add(),
right=BinOp(left=Num(n=33), op=Mult(), right=Num(n=2))), op=Add(),
right=Num(n=1)), op=Add(), right=Num(n=3)), op=Add(),
right=Name(id='a', ctx=Load())), op=Div(), right=Num(n=2)))])

Now we can finally run our visitor on that generated AST the check the LLVM IR output:

1
2
3
4
visitor = AstJit(module, ['a', 'b'])
visitor.visit(node)
visitor.build_return()
print module

Will output the LLVM IR:

; ModuleID = 'ast_jit_module'

define i32 @func_ast_jit(i32 %a, i32 %b) {
entry:
  %mul_t = mul i32 3, %b
  %add_t = add i32 2, %mul_t
  %add_t1 = add i32 %add_t, 165
  %add_t2 = add i32 %add_t1, 1
  %add_t3 = add i32 %add_t2, 1
  %add_t4 = add i32 %add_t3, %a
  %sdiv_t = sdiv i32 %add_t4, 2
  ret i32 %sdiv_t
}

Now is when the real fun begins, we want to run LLVM optimization passes to optimize our code with an equivalent GCC -O2 optimization level, to do that we create a PassManagerBuilder and a PassManager, the PassManagerBuilder is the component that adds the passes to the PassManager, you can also manually add arbitrary transformations like dead code elimination, function inlining, etc:

1
2
3
4
5
6
7
8
9
10
pmb = lp.PassManagerBuilder.new()
# Optimization level
pmb.opt_level = 2

pm = lp.PassManager.new()
pmb.populate(pm)

# Run the passes into the module
pm.run(module)
print module

Will output:

; ModuleID = 'ast_jit_module'

define i32 @func_ast_jit(i32 %a, i32 %b) nounwind readnone {
entry:
  %mul_t = mul i32 %b, 3
  %add_t3 = add i32 %a, 169
  %add_t4 = add i32 %add_t3, %mul_t
  %sdiv_t = sdiv i32 %add_t4, 2
  ret i32 %sdiv_t
}

And here we have the optimized LLVM IR of the Python AST expression. The next step is to JIT that IR into native code and then execute it with some parameters:

1
2
3
4
5
6
    ee = ExecutionEngine.new(module)
    arg_a = GenericValue.int(Type.int(), 100)
    arg_b = GenericValue.int(Type.int(), 42)
   
    retval = ee.run_function(visitor.func_obj, [arg_a, arg_b])
    print "Return: %d" % retval.as_int()

Will output:

Return: 197

And that’s it, you have created a AST->LLVM IR converter, optimized the LLVM IR with the transformation passes and then converted it to native code using the LLVM execution engine. I hope you liked =)

Raspberry Pi no Brasil

* This post is in portuguese

Bom, finalmente chegou meu tão esperado Raspberry Pi, consegui efetuar a compra através de uma fila de espera (estou nesta fila desde o primeiro dia de Março de 2012) na Farnell Newark do Brasil que fez a importação de um (ou mais) lotes da Element 14 e agora está distribuindo aqui no Brasil. Como moro em Porto Alegre no Rio Grande do Sul, o preço total (juntamente com frete) do RPi somaram R$ 182,22 reais, um valor bem acima do esperado para o “computador de $30 dólares”, graças ao nosso gentil governo que como todos já devem ter notado, usa uma EXCELENTE estratégia para incentivar a pesquisa científica, obrigando desta forma os brasileiros a construirem seu próprio hardware usando bambu ou Pau-brasil, mas isto é outra história.

O atendimento da Farnell Newark foi ótimo, a vendedora foi muito atenciosa e sempre respondeu meus questionamentos em um curtíssimo intervalo de tempo, logo após efetuar o pagamento, demorou apenas 1 dia para o aparelho chegar (foi despachado através da UPS). Segue abaixo uma foto dele (clique para ampliar):

Primeiros passos: cartão SD

A primeira tarefa que precisei fazer para fazê-lo funcionar foi a preparação de um cartão SD. Como não consegui encontrar em nenhum lugar que fui um cartão SD de 4GB eu utilizei um micro-SD da Kingston de 4GB (class 4). É importante sempre verificar a Wiki do projeto antes de comprar qualquer cartão SD ou dispositivo USB para o seu Raspberry Pi, pois lá você vai encontrar uma lista de periféricos que comprovadamente funcionam e os que ainda estão problemáticos. Eu aconselho a compra de um cartão class 4 pois houve relatos de problemas com alguns cartões class 10, mas se você já tiver um cartão class 10 não custa tentar a sorte, este é um problema que provavelmente já deve ter sido corrigido no Kernel do Raspbian.

Para preparar o cartão você precisa escolher antes uma distro Linux, eu escolhi o Raspbian que é um port do Debian Wheezy para arm otimizado para “hard float“, o que ajuda bastante na performance de aplicações que fazem bastante uso de operações de ponto flutuante. Além de ser Debian e ter toda a infinidade de pacotes disponíveis no repositório (no momento em que estou escrevendo já existem mais de 30 mil pacotes do Debian já compilados para armhf), ele está funcionando muito bem com todos dispositivos que utilizei até agora (mouse usb, teclado usb, card sd, ethernet, hdmi video/audio, etc.).

Fonte de energia (power supply)

Bom, após ter preparado meu cartão SD eu comprei uma power supply USB, esta da foto abaixo:

Carregador USB “importado”

Para ligar seu RPi você vai precisar de uma fonte USB de 5V com no mínimo 500mA de corrente disponível, não adianta tentar ligar seu Raspberry Pi na USB do computador.

Como nem tudo é tão simples, ao ligar meu RPi ele logo acustou no boot problemas com o módulo ethernet como este e meu teclado USB não funcionava. O RPi ficava simplesmente travado e sem conexão ethernet alguma, os LEDs nem acendiam.

Sempre desconfie da sua fonte de energia em primeiro lugar ao enfrentar problemas como este, ainda mais aqui no Brasil com todas essas fontes de energia USB “importadas”.

Meu primeiro reflexo foi verificar a voltagem que este power supply estava fornecendo, usando os contatos TP1 e TP2 da placa (você pode ver estes contatos como uns buracos na placa na imagem do RPi). O TP1 está ligado no Vin da fonte de energia e o TP2 no GND (terra) da fonte. Ao ligar o voltímetro, ele mostrou a voltagem abaixo:

Voltagem do carregador USB “importado”

Uma fonte de energia que supostamente deveria fornecer 5v estava fornecendo 5.44V, bem acima do limite de +5% ou -5% tolerado por muitos dispositivos USB como teclados, etc. o RPi possui um regulador de voltagem (SE8117T33) que faz a regulagem da entrada de 5V para 3.3V, este regulador tem o 1.1V como voltagem de dropout, ou seja, para que ele forneça um sinal estável de 3.3V ele precisa ter no mínimo 3.3V+1.1V = 4.4V de entrada, até aí tudo bem, pois estamos fornecendo 5.44V, o problema é que este regulador funciona para distribuição de apenas alguns componentes internos do RPi e não para os dispositivos USB e alguns outros componentes (o Vin da fonte é ligado direto aos periféricos USB), ao fornecer 5.44V ele está ultrapassando um limite de 5% que seria entre 4.75V e 5.25V. Este intervalo de voltagem é o ideal para o seu Raspberry Pi, é sempre importante checar se a sua fonte de energia está dentro deste intervalo e afastado dos limites superiores e inferiores. Um dos fatores que pode causar uma queda da voltagem da sua fonte é o próprio cabo micro USB, que acaba atuando como uma resistência, por isso é sempre bom ter um cabo de qualidade (e curto) e uma fonte de qualidade.

No fim da história tive que trocar minha fonte por uma da Samsung que eu já tinha (do Galaxy Tab P1000-L 7″), este da foto abaixo:

Carregador de celular Samsung

Ao trocar o power supply “importado” por este da Samsung (imagem acima), a voltagem agora ficou:

Voltagem do carregador USB da Samsung

Em estáveis 4.91V, dentro limite aceitável. Após esta troca, tudo passou a funcionar perfeitamente e sem nenhum problema. Fica então a dica para quem for ligar pela primeira vez seu RPi.

Eu testei também um carregador de iPad da Apple, que ficou também um pouco abaixo do esperado e decidi não usá-lo, segue a foto do carregador e a voltagem dele abaixo:

Carregador USB da Apple

Voltagem do carregador USB da Apple

 Finalmente boot !

Após todo este trabalho com o carregador, as coisas finalmente funcionaram corretamente e o RPi fez o boot sem problemas como no screenshot abaixo (estou usando uma TV LG de 42″):

Boot do RPi em TV LG (HDMI), clique para aumentar

O RPi tem processadores CPU e GPU realmente incríveis, o boot dele é rápido e a saída na TV ficou realmente muito boa em full hd.

uname no Raspbian

Para testar o processador ARM, que fica em um clock padrão de 700Mhz (você pode fazer overclock até 1Ghz, mas ainda não me aventurei sem um dissipador decente, mas você pode subir para 800Mhz com segurança) eu rodei os benchmarks do OpenSSL, seguem os resultados abaixo:

Benchmark do OpenSSL no RPi

Segue também screenshot do /proc/cpuinfo com os BogoMIPS:

/proc/cpuinfo

No Raspberry Pi (ao menos usando Raspbian) você pode escolher como será feito o split da memória RAM dele, o padrão vem com 128MB para CPU e 128MB para a GPU (processador gráfico), como eu não estou usando tanto o GPU por hora eu fiz um split de 224MB para o CPU e apenas 32MB para a GPU, para fazer isto você só precisa copiar o arquivo de boot em cima do que é utilizadao para o boot (start.elf) e faz um reboot, segue screenshot dos arquivos abaixo, note que o SHA1 do split de 224 é iguao ao do start.elf:

RAM Split (224MB CPU + 32MB GPU)

Após remover 4 dos 6 terminais disponíveis para liberar um pouco mais de memória, a minha memória ficou assim (rodando server do OpenSSH e sem ambiente X):

Memória do RPi após split da RAM

Fiquei muito satisfeito com este split, você ainda pode fazer outras coisas para liberar memória do seu RPi, como por exemplo trocar o OpenSSH pelo dropbear, etc. Aqui tem um ótimo artigo sobre isto.

Algo que não posso deixar passar também é o Python:

Python no Raspberry Pi

 

Arduino vs Raspberry Pi

Muitos vêem o Raspberry Pi como um concorrente fatal do Arduino, a percepção que tive porém foi muito diferente. Acredito que o Raspberry Pi vai ser um ótimo companheiro para o Arduino, você inclusive pode utilizar o Arduino na própria USB do Raspberry Pi ou usar alguma outra interface UART ou algo assim. Tenho muitos projetos em mente pra começar usando Arduino e Raspberry Pi, espero poder ter tempo de postar sobre eles aqui no blog. Para quem está ansioso para comparar o tamanho do Raspberry Pi com o Arduino, segue abaixo um comparativo entre o Duemilanove, o RPi e uma moeda de 1 real (não podia faltar hehe):

Arduino e Raspberry Pi lado a lado

Conclusão

Você provavelmente não encontrará no Brasil um hardware tão bem elaborado como o Raspberry Pi por estre preço (mesmo alto) de R$ 182,00. Recomendo o RPi para todo mundo que tem o mínimo de interesse, eu poderia ficar aqui falando muita coisa sobre o RPi, sobre os polyfuses usados no design dele, sobre a Gertboard que está por vir, sobre as distribuições disponíveis, etc. Logo farei mais alguns posts sobre os projetos usando o RPi também. Espero que tenham gostado da avaliação.