Thursday, November 29, 2012

OpenCL/CUDA: How to resolve "Arguments mismatch for instruction 'mov' "

The following OpenCL kernel fails on my MacBook, CUDA 5.0/OpenCL framework:

__kernel void scalMov(const int N, __global float *x, __global float *y)
{
    const int idx = get_global_id(0);
 if (idx < N)
 {
  x[idx] = 0.1*y[idx];
 }
}

And puts out the error message

ptxas application ptx input, line 38; error : Arguments mismatch for instruction 'mov'
ptxas fatal : Ptx assembly aborted due to errors

There is one easy way to remove that:
__kernel void scalMov(const int N, __global float *x, __global float *y)
{
    const int idx = get_global_id(0);
 if (idx < N)
 {
  float beta = 0.1;
  float alpha = beta*y[idx];
  x[idx] = alpha;
 }
}

The reason for this seems to be the = operation above, which is given some wrong parameters. Funny thing is, this kernel works:

__kernel void scalMov(const int N, __global float *x, float alpha, __global float *y)
{
    const int idx = get_global_id(0);
 if (idx < N)
 {
  x[idx] = alpha*y[idx];
 }
}

So the "mov" instruction only has problems when you are using constants in it.
So if you're having the same problems, try to comment out all your assignments so you can find out which assignment is making problems, then split the assignment up. Note that you have to split it up several times otherwise the OpenCL compiler will "optimize" it back again for you.

Monday, November 26, 2012

Mimicking cout and Java strings in Julia

If you're coming from C++, perhaps you're going to miss cout or some of those fancing ostream stuff in fstream. In Julia, you have print and println, but you have to enclose everything in brackets and the ',' seperation is not really what you're used to when you're coming from C++. I also always enjoyed how easy it is in Java to compose strings. Luckily, it is very easy to incorporate the ostream and String behaviour into Julia, and it also shows some of the nice features of Julia.

cout << "Hello, Julia!\n";

First, we're going to create a singleton named cout. There is a special syntax for singletons in Julia (see here): a type without members.
Next, we'll need a function which handles the operator <<. This works much like in C++, since operators are functions. The function will just take the other argument, and print it:

# our coutType singleton
type coutType
end
cout = coutType()

# the operator <<
function << (c::coutType, t)
    print(t)
    return cout
end

Here we have to apply the same mechanism as in C++: The operator << returns the output object so that chained <<'s are possible. Now we can try our code:

julia> cout << "Hello, Julia! It is " << 
       time()/3600/24/365 << " years since epoch.\n";
Hello, Julia! It is 42.93542962147783 years since epoch.

If you omit the ; at the end, you still have valid julia code, but in the julia shell you will get an output like coutType(XXXX) after your output (in loaded files you won't). That's because the julia shell automatically displays the return values of the last statement. ; is the chained expressions operator , so by inserting a ; at the end you are inserting an empty instruction, which has no return type.
Note that you have to enclose temporary calculations in brackets like for cout << (1+2) << " is " << 3 << "\n"; .

"composing " + "Strings"

Next we want to have something to use strings as in Java: a = "it's the year " + 2012 + "!". For this, we need to specify a function for +:
# + for strings with variable number of arguments
function +(a::ASCIIString, tArgs...)
    for t in tArgs
        a = strcat(a,t)
    end
    return a
end

Here we used Julias nice vargs ability combined with the fact that something like "a"+2+"c" is translated in + ("a", 2, "b").

fstream

Of course you can apply the cout idea to other streams, here's for files:
# << operator for files
function << (out::IOStream, t)
   write(out, t)
   return out
end
# .<< operator for files for writing data stringified (e.g. 2 as "2")
function .<< (out::IOStream, t)
    write(out, string(t))
    return out
end

And again an example:

myFile=open("year.txt", "w")
year = 2012
myFile << "It is the year " .<<  year << ".\n"
close(myFile)

Notice the use of the .<< operator here so 2012 is translated to the string "2012" before being written to the file (otherwise it will write 2012 as binary).

split ostreams

Another idea is to create objects that stream into the console and into a file, which is useful for logging and similar tasks:

type loggerType
    file::IOStream
end
logger = loggerType(open("log.txt", "w"))

function << (out::loggerType, t)
    out.file .<< t
    cout << t
    return out    
end

year = 2012
logger << "Still the year " << 2012 << "!\n"

close(logger.file)



Sunday, July 15, 2012

Julia set in Julia

Julia programming language

Note: working with Julia commit 2013-07-26 (0.2.0-prerelease+2820)

Julia is a new high-level, high-performance dynamic programming language for technical computing.
High-performance assures fast execution, whereas dynamic languages enable fast development.

Both used to be contradictionary features of programming languages, since dynamic basically means no compilation before execution, and that means: More work at run-time. However, since Just-In-Time-Compilers got better and better, now there is a way to have dynamic and high perfomance languages. Julia is one of those languages. They use the LLVM as JIT-compiler - which I think is a pretty neat idea.

Installation is moderately easy as is described here . There are some precompiled packages here, but since Julia is pretty new language, it is best to do a git clone . For that, you might want to update your GCC, since I was not able to compile it with 4.1.2 which comes standard with OSX.

Julia sets

 

So somehow I could not resist in writing a program calculating a Julia set in Julia. Since there was already the mandelbrot example here, it was easy to change it to calculate Julia sets:

julia.jl
# the julia iteration function
function julia(z, maxiter::Int64)
    c=-0.8+0.156im
    for n = 1:maxiter
        if abs(z) > 2
            return n-1
        end
        z = z^2 + c
    end
    return maxiter
end

Since Julia has built-in support for complex numbers, we can now calculate, for example julia(0.5+0.2im, 256)

Sequential Calculation

To calculate a whole picture, we need some for loops like this:
calcJulia.jl
# load image support
include("myimage.jl")

# load our julia function
include("julia.jl")
  
# create a 1000x500 Array for our picture
h = 500
w = 1000
m = Array(Int64, h, w)
  
# time measurements
print("starting...\n")
tStart=time()
  
# for every pixel
for y=1:h, x=1:w
    # translate numbers [1:w, 1:h] -> -2:2 + -1:1 im
    c = complex((x-w/2)/(h/2), (y-h/2)/(h/2))
    # call our julia function
    m[y,x] = julia(c, 256)
end
  
tStop = time()
  
# write the ppm-file
myppmwrite(m, "julia.ppm")
  
print("done. took ", tStop-tStart, " seconds\n");

Unfortuately, there is no image.jl anymore shipped with julia anymore, so here is a very easy version of it:
myimage.jl
function myppmwrite(img, file::String)
    s = open(file, "w")
    write(s, "P6\n")    
    n, m = size(img)
    write(s, "$m $n 255\n")
    for i=1:n, j=1:m
        p = img[i,j]
        write(s, uint8(p))
        write(s, uint8(p))
        write(s, uint8(p))
    end
    close(s)
end

Together with the julia.jl file, you can execute above script with
julia calcJulia.jl

There is an even easier way to calculate the array m:
m = [ julia(complex(r,i)) for i=-1.0:.01:1.0, r=-2.0:.01:0.5 ];
(taken from extras/image.jl). However, above approach yields more insight on the parallel algorithm.

Parallel Calculation 

Parallel programming is not as easy as in, for example OpenMP.  We are creating a distributed array here (darray) and initialize it with the function parJuliaInit, which has to calculate its local part of the array. Because every processor needs to know the init function parJuliaInit and julia, we need to use the @everywhere command for the load and the function definition (@everywhere is not explained in the docs yet):


parJulia.jl
include("myimage.jl")
# we need julia.jl everywhere
@everywhere include("julia.jl")

@everywhere w=1000
@everywhere h=500

# the parallel init function, needed everywhere
@everywhere function parJuliaInit(I)
    # create our local patch
    d=(size(I[1], 1), size(I[2], 1))
    m = Array(Int, d)

    # we need to shift our image
    xmin=I[2][1]
    ymin=I[1][1]

    for x=I[2], y=I[1]
        c = complex((x-w/2)/(h/2), (y-h/2)/(h/2))
        m[y-ymin+1, x-xmin+1] = julia(c, 256)
    end
    return m
end
 
print("starting...\n")
tStart = time()
 

# create a distributed array, initialize with julia values
Dm = DArray(parJuliaInit, (h, w))
 
tStop = time()
 
# convert into a local array
m = convert(Array, Dm)
 
# write the picture
myppmwrite(m, "julia.ppm")
 
# print out time
print("done. took ", tStop-tStart, " seconds\n");



Results

You can run that code with
julia -p 4 parJulia.jl
Where you replace 4 with your number of processors.

Here's a comparison of different processor sizes and algorithms for different picture sizes calculated on a MacPro with 2x 2.26 Ghz Quad-Core Xeon processors (= 8 processors in total):
 
code #processors time 500x1000 time 2000x4000
calcJulia.jl 1 2.20 s 34.50 s
parJulia.jl 1 3.16 s 46.26 s
parJulia.jl 2 1.83 s 23.64 s
parJulia.jl 4 0.92 s 7.28 s
parJulia.jl 5 0.83 s 5.27 s
parJulia.jl 8 0.85 s 2.97 s
parJulia.jl 10 0.81 s 2.50 s

The table shows the difficulties in parallel computing: Even if the algorithm scales perfectly in theory, the execution on N processors is not always N times faster. This is because of not all parts of your implementation and your hardware might scale perfectly, especially not for all problem sizes (very large or very small). The drastically difference of access rates for the L1/L2/RAM memory can even lead to results like the parallel calculation of the 2000x4000 image, which is 15 times faster on 8 processors than on one.

Conclusion

Julia is a nice language with a MATLAB-style syntax which could have a big influence on scientific computing. Many applications are operating on the memory bandwith limit, or the communication bandwith limit, so with a JIT compiler, those would be just fine.

Note: Syntax highlighting is done with Syntax Highlighter and this little beta JavaScript configuration file for the Julia language.

Update 1:
Syntax Highlighting should now work.
Update 2:
Fixed sequential calculation.
Update 3:
Fixed parallel calculation. load() is not @everywhere by default.
Update 4:
Now working with Julia commit 2013-07-26, which changed DArray syntax and require.

Saturday, July 14, 2012

gcc name demangling

According to wikipedia, name mangling is a "way of encoding additional information in the name of a function, structure, class or another datatype in order to pass more semantic information from the compilers to linkers".

The need for name mangeling arises because the name of a symbol in a file is very restricted. It can not contain spaces, brackets or columns, for example. With name mangling, the linker is able to distinguish overloaded functions in C++ like
int bla();
int bla(double);
The wikipedia article and this describe name mangling quite well.

You'll see a lot of mangled names when you try
nm someexecutable

So I created a small C++ program demangles the names. Save below code in a file named mydemangle.cpp, and compile it with
g++ -o mydemangle mydemangle.cpp

Now you can try it with
mydemangle _ZN9wikipedia7article6formatEv
and the result is
wikipedia::article::format()

But demangle can do more: It can read input from stdin. So you might try
nm someexecutable | mydemangle 

Now mydemangle demangles all names it can demangle and leaves the rest as it is.

There's a quite handy way in C++ to demangle names via the function
char * __cxa_demangle (const char *mangled_name, char *output_buffer, size_t *length, int *status);


Be aware that this will not be available for all processors/compilers.



Here's the code:

mydemangle.cpp

#include <iostream>
#include <cxxabi.h>
#include <stdlib.h>
#include <string>
#include <stdio.h>
using namespace std;
int main(int argc, char *argv[])
{
    int status;
    if(argc == 2)
    {
        // we have one argument: demangle it
        char *realname = abi::__cxa_demangle(argv[1], 0, 0, &status);
        if(status==0)
            cout << "\n" << realname << "\n";
        else
            cout << "\ncould not demangle " << argv[1] << "\n";
        free(realname);
    }
    else
    {
        // we have no argument: read from stdin
        char c, lastc=0x00;
        string s;
        while((c = getchar()) != EOF)
        {
            // mangled names start with _ . consider only if last sign was space or tab or newline
            if(c == '_' && (lastc==' ' || lastc == '\n' || lastc == '\t'))
            {
                s = "_";
                // add all characters to the string until space, tab or newline
                while((c = getchar()) != EOF)
                {
                    if(c == ' ' || c == '\n' || c == '\t')
                        break;
                    s += c;
                }
                // some compilers add an additional _ in front. skip it.
                const char *p = s.c_str();
                if(s.length() > 2 && s[1] == '_') p = p+1;
                char *realname = abi::__cxa_demangle(p, 0, 0, &status);
                if(status==0)
                    cout << realname; // demangle successfull
                else
                    cout<< s; // demangling failed, print normal string
                free(realname);
            }
            cout << c;
            lastc =c;
        }
    }
    return 0;
}

Of course, there is some easy way in bash to do it. This requires demangle (part of KDE Dev Kit) and is not as fast and convenient as above method.
case 
#!/bin/bash
while read LINE
do
    for WORD in $LINE
    do
 echo -n $WORD | demangle
    done
    echo
done

Wednesday, July 4, 2012

Ultimate bash prompt

The standard bash prompt on most systems is very unusable. Most of the time, it's just something like bash-3.2#, which doesn't give you much information. Knowing the machine you're working on and your current working directory is crucial, and if your prompt provides you this information this can make your life a lot easier.

So here it is: My bash prompt. It looks like this:

in GNOME

on mac (Terminal.app)
Features are:
  • Display of hostname up to first '.'
  • Display of path
  • red SU in front when superuser/root
  • display of hostname up to first '.' and directory in xterm/mac title
In my opinion, that's all information you need most of the time (except for maybe some git/svn information). I added the shortened hostname in front because i'm working on different systems a lot and this just helps distinguish them from the window title.
You can add more to it, flashing colors and stuff, but it just gets unusable at some point especially when you have long directory names.
Here is the code: 
#!/bin/bash
# this sed line returns everything up to the first . in hostname
# ex. linuxbox.university.gov -> linuxbox
SHORT_HOSTNAME=`hostname | sed 's/\([^\.]*\).*/\1/'`

#LONG_HOSTNAME=`hostname -f`

NOCOLOR="\[\e[0m\]"
BRACKETCOLOR="\[\e[1;30m\]"
DIRCOLOR="\[\e[1;34m\]"
HOSTCOLOR="\[\e[1;32m\]"

# add SU in red if root/superuser
[[ $EUID -eq 0 ]] && HOSTCOLOR="\[\033[1;31m\]SU $HOSTCOLOR"

# command executed just before bash displays a prompt
# here it is set to change xterm's (also mac terminal) title string to
# hostname currentDirectory
PROMPT_COMMAND='echo -ne "\033]0; $SHORT_HOSTNAME `dirs`\007"'

# the prompt
PS1="$HOSTCOLOR$SHORT_HOSTNAME $BRACKETCOLOR[$DIRCOLOR\w$BRACKETCOLOR] $NOCOLOR"
You can just copy it in your ~/.bashrc or save it as ~/prompt.sh and add a source prompt.sh in your ~/.bashrc .

Note: Of course this is not the ultimate bash prompt, every advanced user will have an own customized prompt. But I hope it's a good place to start :-).

Here's some more information:
http://wiki.ubuntuusers.de/Bash/Prompt
https://wiki.archlinux.org/index.php/Color_Bash_Prompt

Enjoy!
- Martin