16
Aug
11

Prefix Sum Using OpenMP

OpenMP is an API for shared memory parallel programming. As in the various threads running on various cores or processors have memory space that is accessible by every thread, in addition to each thread’s own private memory space. It is available for C/C++ and Fortran.

Arguably, it is easier for parallel development than MPI, Pthreads etc. (And moreover, it is the one with which we’ll start our Parallel and Distributed Computing lab).

Some Basic Constructs

  • parallel : most basic construct. Creates a team of threads to execute the code that follows this directive, and all threads execute the code.
  • for : used just before a ‘for’ loop. Runs the iterations of the loop in parallel by splitting them amongst available threads.
  • barrier : used to provide barrier synchronization. Threads wait here until all threads in the team have finished execution.
  • single : only one thread executes the following block of code. Rest of the threads wait at the end of the construct.
And yeah, just in case this is your first time, don’t try to run these programs as you normally would. Compile from the command-line with -fopenmp flag.

First Non-Trivial Program

Formal Statement:

Given an array A[1..n], return an array S[1..n] such that S[i] = A[1] + A[2] + … + A[i] for all 0<i<n+1

For example:

Given the array [5,8,7,2,3], output will be [5,13,20,22,25]

Basic Parallel Algorithm:

  1. for j in (1 to log2(n))
  2.     for i in (j to n)
  3.         S[i] = A[i] + A[i – j]
  4.         i = i + 1
  5.     j = 2 * j

First attempt:

This code tries to simply use the most obvious parallelism in the algorithm. Steps 2 and 3 of the algorithm are shared between threads, each thread working on a different subset of the array. And yeah, to prevent race conditions, we use an auxiliary array which stores writes from a thread while other threads are reading from the other array.

#include <stdio.h>
#include <omp.h>

int main()
{
  int n, ar[2][100], *t, i, toread, size, j;
  printf("Enter length:");
  scanf("%d", &n);
  printf("Enter numbers:\n", n);
  for(i = 0; i < n; i++)
    scanf("%d", &ar[0][i]);
  /*set up complement to array that holds values*/
  toread = 1;
  /*copy first value, since it is not copied by the code*/
  ar[1][0] = ar[0][0];
  size = 0;
  /*following loop aims to get log2 of size, but can be avoided as in 2nd program*/
  while(i) {
    size++;
    i >>= 1;
  }
  /*following code implements algorithm*/
  for(j = 0; j < size; j++) {
    toread = !toread;
    if(toread) t = ar[0];
    else t = ar[1];
#pragma omp parallel for default(none) private(i) shared(n, j, t, ar, toread)
    for(i = 1; i < n; i++) {
      if(i - (1 << j) >= 0)
	t[i] = ar[toread][i] + ar[toread][i - (1 << j)];
      else t[i] = ar[toread][i];
    }
  }
  toread = !toread;
  for(i = 0; i < n; i++)
    printf("%d\n", *(*(ar + toread) + i));
  return 0;
}

Second attempt:

Here, we’ll divide the original array into sub-arrays, the number of which will be equal to the number of threads provided by the environment. Each thread will, linearly, calculate the prefix-sum for its assigned sub-array. These prefix-sums will be less than the actual sums, since elements before the start of a particular sub-array are ignored.

Now, the last elements of each of these sub-arrays is stored in another array. For this array, the prefix-sum array is calculated, and the corresponding values in original array are updated. This is done by adding to each element the requisite amount that was missing earlier.

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#include <string.h>

int main()
{
  int *arr, *partial, *temp;
  int num_threads, work, n;
  int i, mynum, last;
  printf("Enter length:");
  scanf("%d", &n);
  if(!(arr = (int *) malloc (sizeof (int) * n))) return -1;
  printf("Enter numbers:\n");
  for(i = 0; i < n; i++)
    scanf("%d", arr + i);
#pragma omp parallel default(none) private(i, mynum, last) shared(arr, partial, temp, num_threads, work, n)
  {
#pragma omp single
    {
      num_threads = omp_get_num_threads();
      if(!(partial = (int *) malloc (sizeof (int) * num_threads))) exit(-1);
      if(!(temp = (int *) malloc (sizeof (int) * num_threads))) exit(-1);
      work = n / num_threads + 1; /*sets length of sub-arrays*/
    }
    mynum = omp_get_thread_num();
    /*calculate prefix-sum for each subarray*/
	for(i = work * mynum + 1; i < work * mynum + work && i < n; i++)
      arr[i] += arr[i - 1];
    partial[mynum] = arr[i - 1];
#pragma omp barrier
    /*calculate prefix sum for the array that was made from last elements of each of the previous sub-arrays*/
	for(i = 1; i < num_threads; i <<= 1) {
      if(mynum >= i)
		temp[mynum] = partial[mynum] + partial[mynum - i];
#pragma omp barrier
#pragma omp single
      memcpy(partial + 1, temp + 1, sizeof(int) * (num_threads - 1));
    }
    /*update original array*/
	for(i = work * mynum; i < (last = work * mynum + work < n ? work * mynum + work : n); i++)
      arr[i] += partial[mynum] - arr[last - 1];
  }
  for(i = 0; i < n; i++)
    printf("%d\n", arr[i]);
  return 0;
}
Advertisements
13
Jun
11

Oracle Apex–first brush and some niceties

Working on another project. This time it uses a relatively easy, and inconspicuous(at least for me) technology from Oracle®, that runs on top of the Oracle database. Known as Application Express, in short ApEx.

Basic Intro:

You can get the official information here… In my words, ApEx is a tool that allows you to build browser-based applications, running on top of the database and interacting with it, and all this requires no knowledge whatsoever of web-technologies(although HTML and JavaScript may help). It’s a RAD-tool, and it indeed lives up to this classification.

Features I Loved:

  1. Almost as simple as writing SQL and/or PL/SQL, with the added benefit that you get a GUI in your app with minimal effort.
  2. Greatly simplified model for an application:
    1. Pages: the basic building blocks
    2. Regions: contained within pages, act as containers for items. There are various types of regions: HTML, report, calendar, forms etc..
    3. Items: Actual items that hold your data
    4. Processes, Computations and loads of other stuff
  3. Wide range of items, that support almost any task you may want to do.
  4. Amazingly intuitive interface for designing and modifying your application..
  5. Drag and drop method of layout design if you’re into it.
  6. Subtle, well tuned, and close to exhaustive list of attributes for everything you create.
  7. SQL Workshop: Contains:
    1. Object Browser: lets you view all objects in your database, and their details.
    2. SQL Commands: the old and trusted sql command center. Run anything you want here.
    3. SQL Scripts: just in case you want to run a long list of commands, repeatedly.
    4. Query Builder: build your query graphically.

Tips(if you’re beginning apex)

  • Get to know the basic interface before you begin development.
  • Create a test application on a miniature scale to get a feel. You’ll save tons of time later on. Trust me!!
  • Keep a handy list of your database objects, or, better still, open up the object browser in ApEx while you’re working.
  • Follow a nice and handy naming convention for all your objects. Great time-saver.
  • If you want to do something with apex, and you can’t find a way, make a way. This thing is so customizable, that apart from changing the “nitty-gritty-html-javascript-css” stuff, almost anything can be accomplished with ease and some creative thinking.

Some Issues:

  1. You can have great control over most of your application, but the UI is still mostly out of your hand unless you’re willing to get down into the mud.
  2. Apex will add some overhead to the queries that you’ll run through it. Not much though.
  3. Creating an application is also through a browser, and this means at least some fretting over page rendering delays and stuff like that.
If you have an Oracle database, chances are, Apex can improve your efficiency in dealing with your database for simple tasks. Use it if possible.
22
Mar
11

How to Develop A “First Application” for Android

Me liking Python doesn’t make Java any lesser of a language…

Yeah, as usual, it is another of the projects that I “HAD” to undertake. Not for grades this time though. Just helping one of the professors along…

AIM:

Given an excel spreadsheet of sampled values of a waveform, recreate the moving waveform on an Android display. More than one concurrent waves may be there.

Preparation:

  1. Download Android SDK and AVD manager from http://developer.android.com and install it.
  2. From within the above tool, download some stuff, specifically, the samples, desired SDK platforms, and documentation.. Hefty >200 MB download though.
  3. Set up Eclipse ADT plugin. (This is a blessing for Android development)
  4. Start digging through the documentation.
  5. Plan out your approach.
  6. Do the Hello World tutorial.

Creation (specifically for my project):

  1. Used the SurfaceView class as drawing surface for the animation. Seemed simple against the other alternatives.
  2. Used Path class to recreate waveform from points(at this moment, random points, data is not yet available).
  3. Test.
  4. Used Apache POI (User model) to convert excel spreadsheet data into a Java understandable format.
  5. Changed code written in step 2 to take input from step 4 and display non-random, user-supplied data.
  6. Quite notable is the fact that the storage options on Android are varied, and suitable for a wide variety of uses. I chose by my personal taste, the Internal Storage. The aim being not persistent storage across invocations, but persistence while the data is being readied for presentation.
  7. Integrated everything.
  8. Test.

Work Still To Be Done(in my project):

  1. Performance Sucks: As soon as I’ll put some labels/controls on the SurfaceView, my performance will hit rock-bottom. Still trying to figure a way out.
  2. Usability: Some work on User controlled customization, like animation speed, pause etc. is not done.
  3. Storage: My current storage solution is not even a storage solution. Its just a dumpster :D.. If I go public with this, I’ll need a better and more logical storage architecture.

Time Taken:

I’m writing this 11 days into the task. Out of which most of the days were wasted in lazying around. Engineering you know.

And just today, the Professor came to my room to see the progress 😀 That’s a first

If you’re one of the guys who’ll foolishly wanna ask me for help, see ways to really contact me here..

Conclusion:

  • Android has one of the best documentations around, and trust me when I say, I’ve read some good ones.
  • Easy to build and test once you know Eclipse and Android Debug Bridge
  • You’ll never ever complete a project without Open Source technologies if you’re not working on .Net (I used Apache POI)
  • Java is still slow. Faster than last I checked on my Symbian (:P) but still slow.
  • Google rocks. Always.
04
Jan
11

Chatting Alice

Happy New Year people 🙂

Towards the extreme rear end of last year, I created a small web app, Chatting Alice, which is basically a jabber/XMPP client that allows the user of the app to chat with publicly available chat-bots on this site.

Anybody with an XMPP enabled chat client and a jabber/GTalk account can simply add chattingalice@appspot.com and start chatting…

Features:

  • A menu based interface (from within the chat) that provides options to easily change bots, and see current bot.
  • Various bots, selected on the basis of the most popular bot statistics on www.pandorabots.com
  • Each user sees his interaction as independent of other users, since chat contexts are properly maintained with different accounts for each user.
  • Chat history is not recorded, for obvious reasons 😛
  • Easy to start and stop using

Development:

I happened to be searching around for a suitable time-pass last December. I looked for some chat-bots too. There were many, but there wasn’t any easily accessible interface for them. So, I made one.. I wanted to work on App Engine, and hence the app was born.

Chatting Alice is hosted on Google App Engine, and out of the Java and python runtime choices, it is running on the python sister.

App Engine provides an XMPP service to its apps, with the facility to send invites, receive or send chat messages, and checking the availability of a user (GTalk ID). This api was used to interface with the publicly available chatbots on pandorabots. Each chat request to Chatting Alice is followed by a request to pandorabots’ server, which then sends a reply. That reply is then forwarded to the user.

The most complicated part was creating a proper system to separate chat accounts for various users, so context was not lost if 2 simultaneous users were chatting with the same bot. This was done by way of some datastore (app engine’s data storage system) entities that provide necessary details to pandorabots at the time of each request, which helps keep chatting contexts separate.

Last feature to be added was multiple bots, and the menu interface. Not that time-consuming, as python made it pretty easy to handle textual commands and errors.

Current status:

Since this was nothing but an impulsive experiment, development has been stopped. If further uses occur to me for this app at the backend of another app, maybe I’ll get back to it. BUT THE APP IS WELL AND RUNNING, WITH 10 BOTS as of now.

If you find any bugs/missing features, I’ll be happy to fix them (if possible) since as it is, I’m still learning.

Please let me know of any such issues at this Facebook page

23
Nov
10

My First Lexer (in Python)…

There is a course we have, Theory of Computations (actually more of formal languages), which uses the Cinderella Book as one of the recommended readings. There was an assignment for this course, which involved designing a program to separate tokens from a C++ program. After a little search-engining, I found out that such a program is actually a lexer(lexical analyzer), uses regular expressions, and that there are various automated tools to generate lexers.

But I decided to design one on my own before looking into the lexer implementation strategies in detail. So, I began with reading some stuff from “Engineering a Compiler”, and got something running. Here is the crude working code. Its immensely unproductive as far as applicability goes, but I was behind schedule in submissions, so I crooked my way through. As soon as possible, I’ll work on a better implementation.

Source Code:

Click below to read:

import re
from deftok import keywords,expressions,separators
import os
    
tokens=[]

def matchNow(line,pos,id):
    """
    checks for the regular expression of the given 'id', if it is present in rulebase
    otherwise appends it to token list
    also adds type of token to tokens list
    """
    global tokens
    ret=0
    if id in expressions.keys():
        pattern=re.compile(expressions[id])
        found=pattern.match(line,pos)
        tok=line[pos:found.end()]
        ret=found.end()
    else:
        tok=id
        ret=pos+1
    if tok in keywords:
        b='KEYWORD'
    elif id=='i':
        b='IDENTIFIER'
    elif tok in separators:
        b='SEPARATOR'
    elif id=='n':
        b='NUMERAL'
    else:
        b='OPERATOR'
    tup=(tok,b)
    tokens.append(tup)
    return ret

def checkLine(line,pos):
    """
    removes whitespace
    checks first character of line at 'pos', and calls matchNow() appropriately
    """
    global tokens
    pattern=re.compile('\s+')
    found=pattern.match(line,pos)
    if found:
        pos=found.end()
    if pos<len(line):
        curr=line[pos]
    else:
        return
    endofprev=pos
    if curr.isalpha() or curr=='_':
        endofprev=matchNow(line,pos,'i')
    elif curr.isdigit():
        endofprev=matchNow(line,pos,'n')
    elif curr in ['@','$']:
        endofprev=pos+1
    else:
        endofprev=matchNow(line,pos,curr)
    checkLine(line,endofprev)

def main(name):
    """
    responsible for file handling, and concatenation of lines with backslash-newline
    """
    fp=open(name,'r')
    temp=""
    for line in fp:
        if len(line)>1 and line[-2]=="\\":
            temp=temp+line[:-2]
            continue
        line=temp+line[:]
        temp=""
        checkLine(line,0)
    fp.close()
    fp=open('outputof'+name+'.txt','w')
    for token in tokens:
        token1,token2=token
        fp.write(token1+'\t'+token2+'\n')
    fp.flush()
    os.fsync(fp.fileno())
    fp.close()
    
if __name__=="__main__":
    import sys
    main(sys.argv[1])

Here is the definitions file. It has a list of keywords and separators, and a dictionary mapping “id’s” with regular expressions…

#list of keywords
keywords=['auto', 'const', 'double', 'float', 'int', 'short', 'struct', 'unsigned', 'break', 'continue', 'else', 'for', 'long', 'signed', 'switch', 'void', 'case', 'default', 'enum', 'goto', 'register', 'sizeof', 'typedef', 'volatile', 'char', 'do', 'extern', 'if', 'return', 'static', 'union', 'while', 'asm', 'dynamic_cast', 'namespace', 'reinterpret_cast', 'try', 'bool', 'explicit', 'new', 'static_cast', 'typeid', 'catch', 'false', 'operator', 'template', 'typename', 'class', 'friend', 'private', 'this', 'using', 'const_cast', 'inline', 'public', 'throw', 'virtual', 'delete', 'mutable', 'protected', 'true', 'wchar_t']

#list of separators
separators=['(', ')', '[', ']', '{', '}', ',', ';', ':']

#rulebase
expressions={   '+':r'\+[+=]|\+',
 '-':r'-[-=>]|-',
 '!':r'!=|!',
 '*':r'\*=|\*',
 '/':r'/=|/',
 '%':r'%=|%',
 '<':r'<<=|<[<=]|<', '>':r'>>=|>[>=]|>',
 '&':r'&[&=]|&',
 '^':'^=|^',
 '|':r'\|[|=]|\|',
 '=':'==|=',
 'i':r'[A-Za-z_]+\w*',
 'n':r'[0-9]+\.[0-9]+|[0-9]+',
 '.':r'\.[0-9]+|\.'}

Problems with this program:

  1. It is ugly.
  2. Tokens like “9xyz” are accepted as valid identifiers. Change in regular expressions required.
  3. Apart from the regular expression rulebase, not much of the code is customizable. Eg: classification of identifiers is rigid, formatting in output file is precoded; in fact, even the rulebase is forced to work according to the inbuilt functions: checkLine() and matchNow()
  4. Invalid tokens need to raise an exception, not included here.
  5. Possibly, the entire lexer should be packaged in a class, which is iterable over itself. Then, its instance can be utilized as <instancename>.next()

There might be other issues as well. After I get over my exams, lets see if I get a better version of this rudimentary lexer up and running.

Namaste.

19
Nov
10

int main()

“The trouble with programmers is that you can never tell what a programmer is doing until it’s too late.”
Seymour Cray

It’s an interesting activity, programming. Gives you the butterflies if you think about it: a piece of electronic equipment can be made to so many interesting things, only if you know what it can do, and how to make it do so.

It’s not easy though to learn good programming. It’s so much easier to become a crappy coder.

I know the tiniest amount about this majestic art. But I’m willing to learn. And what better way to learn, than to share whatever I’m picking up and doing, with as many people as I possibly can. There are 2 things I can gain:

  1. If I have to discuss my style, my code, or my thinking, I’ll at least be marginally critical about it, which is way way better than accepting things without scrutiny.
  2. The better reason: I hope that as often as possible, someone might point out a better way to accomplish the task at hand. PRICELESS!!

Plus, I won’t be feeling like I’m on a solo mission-to-mars with no one to tell my stories to 😛

(Phew. The first post is so much tension.)

Lets Code!!