Home

Study

Parallel QuickSort with OpenMP and Cilk++

March 13, 2009 by xman
Posted in

The introduction of omp task in OpenMP 3.0 allows easy parallelization of the famous quick sort algorithm. As OpenMP 3.0 support in GCC is relatively new, I like to compare its performance particularly the omp task with a commercial compiler Cilk++ which is designed to efficiently support spawn/sync mechanism. Conceptually, the omp task and the Cilk++ spawn/sync are very similar.

Quick sort chooses a pivot, partitions elements into [< pivot] & [>= pivot], and sorts the two partitions recursively. The implementation in my experiment performs partitioning sequentially, and sorts the two resulting partitions in parallel.

Experiment setup:

  • AMD64 Phenom X4 9950 (2.6GHz)
  • Fedora 10 x86_64
  • GCC 4.4 svn revision 144773
  • Cilk++ 1.0.2

Parallelizing Recursive Fibonacci using OpenMP and Cilk++

March 11, 2009 by xman
Posted in

OpenMP 3.0 has added an interesting construct called omp task, while Cilk++ is a compiler developed by Cilk Arts to easily parallelize a C/C++ program. It is interesting to see how we can parallelize the following simple fibonacci program.

Serial:

long fib_serial(long n)
{
    if (n < 2) return n;
    return fib_serial(n-1) + fib_serial(n-2);
}

Ideas for Supercomputing

February 24, 2007 by xman
Posted in

Not enough computers to run your compute intensive simulations? 3D graphics rendering? DNA sequencing?

There are a bunch of computers readily for use most of the time.

  • Cybercafe
  • School library
  • Office at night

Research institutes, 3D graphics studio, ... often run out of hardware resources. Can they simply pay those owners of idling computers and run their tasks on these computers?

Perhaps this can boost the revenue of cybercafe. :) It's a win-win situation for both parties.

Linux 2.6 Scheduling Algorithm Sketch

November 19, 2006 by xman
Posted in

Scheduling classes:

  • Real-time FIFO
  • Real-time RR
  • Conventional time-shared

Processes running in conventional time-shared:

  • Static priority, sp \in [100,139] \Rightarrow use to compute quantum duration, Q.
    Q = \left\{ \begin{array}{ll} (140 - sp) \times 20 & \mbox{if sp < 120} \\ (140 - sp) \times 5 & \mbox{if sp \geq 120} \end{array} \right.
  • Dynamic prority, dp = \max(100, \min(sp - bonus + 5, 139)) where bonus \in [0,10]
    • Bonus is computed based on the process average sleep time. Effectively, a process sleeps more will get more bonus, utilizes CPU will decrease its bonus.
    • Use with static priority to determine if a task is interactive (dp \leq 3 \times sp / 4 + 28).
    • Dynamic priority is looked up by scheduler to select a new process to run.
  • Active & expired processes
    • When a process uses up a quantum, if the process is active batch, it will be transferred to expired list; if the process is active interactive, it will usually remain in active list.
    • An active interactive process will be transferred to expired list if the eldest expired process waited for a long time, or has higher static priority.

Processes running in real-time:

  • Real-time priority \in [1,99]
  • Always favor higher priority runnable processes.
  • Always active.
  • Time quantum depends on static priority.
  • Does not calculate dynamic priority.

Priority array:

  • Maintains active and expire priority array.
  • For each priority in a priority array, it maintains a list of associated processes.
  • When the active priority array becomes empty, the scheduler can just swap the active and expire arrays with merely pointer assignments.

Reference:

  1. Linux Kernel Development by Robert Love
  2. Understanding the Linux Kernel by Daniel P. Bovet, Marco Cesati

S3Xiao

September 24, 2006 by xman
Posted in

S3Xiao is our class. Inside has our head quarter, our gangs, our ways of working, ......



The Hurdle of getting a PhD

March 23, 2006 by xman
Posted in

Friend x: You are now working or studying?
xman: I'm now working in full-time basis, and studying in part-time basis. :)
Friend x: Not bad huh! 8) Getting a master?
xman: No. I'm getting a PhD. :D
Friend x: Wow! PhD can do part-time 1? :o When are you going to finish that?
xman: mmm.... may be 2 years later. :? (it's just a random number, I wouldnt know if I'm able to complete it at all. :( )

Theory vs Practice: Part I
Theory says: Assuming this and that, ignoring those and all those, we can show that method A works much faster than method B. 8) Hooray! :) We rigorously proved something. 8) My theoretical results looked beautiful like art, covering much wider range, and can sustain much longer than your experimental results. When you upgrade your machines, every 4 years??, you'll have to re-run all your experiments. :( What a boring task for a short lifespan of results! :?

Practice says: Given this set of data, information, given an old machine, my experiments tell method B works up to m times faster than method A for all the data set I've tested :o . It seems that we should use method B instead }:) , luckily I didnt blindly following your theory! }:) Obviously, your assumptions do not hold for my case, what you are ignoring can have 'butterfly effect'. What a beautiful theory, yet hardly useful in practice! :? Who cares with those mathematics in your papers. :?

Theory says: Well, your results are valid only on your old machine. New machine might show your results no longer useful. 8) How many experiments can you afford? :? Experiments on all diffferent types of machines in the world? :? How many types of methods can you afford, there might exists a method C that's much more superior than your A and B. How much time it takes to run one experiment? :o Why should I trust your numbers published in the paper? :? How do you explain the special curves in your graph plots? :o If your job is merely running experiments, why do you need to do PhD? :o }:) I can pay a low cost engineer for that.

...... to be continue ......

Learn to GOOGLE

March 15, 2006 by xman
Posted in

Friends asking me when am I going back to KK :? . Friends also asking me what am I going to contribute to KK :? . ...... Frankly, ...... I dont know. Honestly, I never think of doing business since young. I just like to play this and that, have fun, not aiming to earn people's money. Tell you but you may not believe, I dont feel good when I win people's money during CNY :p , as a result, I always loss what I won, and a bit more from my pockets at the end.

I started reading The Google Story recently. Staffs are inline-roller-blading, cycling in their campus. Staffs are playing hockey, volley ball, ...... Staffs are no more than 100 feet from food. Staffs have 3 free meals a day. ...... One of their staff said, he is not use to eating outside anymore, that he has to PAY, in order to get food. :p ...... Yet they are earning billions dollars. If Yahoo!, AltaVista, ...... realized their potential early, they would have licensed the technology early. ...... :o Even the giants at that time missed the bonanza and get even richer.

It's interesting to see they initially just concentrated much on solving searching problem. Once they devised the ways to do it well, opened it for public try, they were getting popular even without doing advertisements :o . Their search engine became the default search engine for many Stanford professors, students ...... and now they diversify their work into many areas.

I dont know how much potential I have, or rather, do I have any potential at all. I shall not be greedy and think too much on how to earn people's money. I think I should just concentrate on solving problems, contribute to the society. Once we are able to do something extremely well, 'gold mine' will be following on the way by itself. I should spend more time innovating than spending time to think what makes money, what doesnt. :p Remember, even the BIG BOSS missed the bonanza.

Hunting for Lecture

August 5, 2004 by xman
Posted in

Vocab of the post:
ooo gui -- oh my god.
baru -- new, or only.
zadao -- unexpected things happened.

I'm taking a subject for this semester. Last Wed, I had dinner with friends :) . At that night baru found that, my first lecture start at night!!! ooo gui, I miss the first lecture!!! I thought lecture schedule at every Thurs. Aiiiii, .... uiiiii, the lecture can be downloaded from the web weeer :D , hehehe. The NTU ah, bought lecture video from other Universities to conduct courses :? . Ok, that's still not that bad, at least I didnt miss any technical things. :)

... Yesterday was Wed, I went to the lecture, LT08.... eeeee, how come no people one??? :? Did I see the venue wrongly just like I see the schedule???? :? ok, let me check it on the web in my lab. mmm....it's really LT08. I went back LT08 again, really no people there. :? What's the arrangements? No good announcements on the web at all. The announcement only said we can borrow the lecture video CD from the Digital System Lab. :( Do I really have lectures to attend? How's the arrangement for the lab session? What about tutorials? :? .... I tried to find who is my classmates, but I couldnt find any. Ahhhh, the subject is only offered to part-time students. All my friends I'm aware are full-time students. :p .... Nvm, I just go home then. It was 8:00pm in the lab.

....eeeeeee, I can email to others who are also taking the same subject through the web portal weer... hehe.... good good... .... :o So it's really self study subject. Watch the video by yourself. 18 Aug come back for discussions. Need to come back only if you have questions!!!! waaaah, real zadao. :( OK then. At least I'll not be scolded by the professor who knows me!!! During undergraduate study, the professor like to ask me to answer tutorial questions. Probably he only knows my name. Due to last time, he was shocked to see me still in the lecture even at one day before CNY. He thought I asked people to help me to sign the attendence!!! During the lecture, he asked, "Waah, you didnt go back ah?" ...

It's again a great weekend

May 29, 2004 by xman
Posted in

It's again a great weekend. The morning was spent in the extra ordinarily cold meeting room in NTU. After staying more than 5 minutes in the room, my skin lost all the elasticity. My fur stood up straight. My dear x-NTU classmate took most of the time to report her progress in her one week research. Haha, as I had expected, I didnt have a chance to present again (though I really didnt prepare anything to present :p).

However, next week I probably will be the first one to present. So, I die die have to come out with something new for my research in this week. And someone has to provide snack at next meeting, as we always complain hungry when someone is presenting. So I should bring some snack for the next meeting? at the same time to bribe them not to ask many questions 8)

Today was a lucky day

May 28, 2004 by xman
Posted in

Today was a lucky day. There was no train fault, no more smelly hair, no more late to office, but it was a rainy day. I always have my umbrella ready at my bag, so not a problem :). It'll be especially useful when the girls in company didnt bring their umbrella.

Today was the last day of the training course. We actually left very little material to cover. ("What to do? Ah ha, just keeps on chit chatting will kill the time easily") .... 4:00pm, the chit chatting session ended with warm good byes. Haha, good, what a great relief. But they still asked whether I have other courses to be conducted in the future :o. ("Why would someone like to attend such a boring training course?")

Today was declared as the family week. Everyone could leave the company at 5:00pm (usually 6:00pm). Mmmm, even though I dont have family to dine with, I still can go back early to have a good sleep. Arrrr, I always afraid of Friday. Every Saturday I'll go to school to meet professor and friends in a weekly meeting. And I've nothing to present again :(.

Anyway, that's the business of tomorrow. Tire then I must sleep, hungry then I must eat.

Syndicate content