Once upon a time, in a far away village lay a dying old man. He called his sons to his deathbed and spoke to them one last time. He said “Sons, see that bundle of sticks? Each one of you try to break it. The one who can break it will inherit all my riches”. Each son, being greedy, wanted all the riches for himself. So each one of them tried to break the bundle of sticks but none of them succeeded. The old man asked his servant to untie the bundle and said to his sons, “Each one of you now get one stick and break it”. Without any effort, each son was able to break the stick. The old man said “You see, when you unite, no task will be difficult. The riches that I told you was a lie. We are broke. When i’m dead, make sure you unite so that you can survive.”
Fast forward to modern times. You can think of the bundle of sticks to be a complex problem that is itself composed of smaller problems. The sons are the processors of your computer. When each processor was given the task to solve the complex problem, it fails to solve it in a reasonable amount of time. When the complex problem is decomposed into smaller problems and given to each processor, each processor is now able to solve the smaller problems quickly thereby solving the big problem quickly as well.
The process of decomposing a problem into smaller problems and solving them in separate processors is called Parallel Computing. In this article, we will compute how fast a certain algorithm will run when parallelized. The problem we want to investigate is sorting an array of a million (
Efficient Sorting
Suppose you have an array 
Since the height of this binary tree is lg(n!), then we have
![\lg(n!) = \lg\Big[ n \cdot (n - 1) \cdot (n-2) \cdots 1\Big] \le \lg n + \lg (n-1) \cdots \lg1 \le \underbrace{\lg n \cdots \lg n}_\text{ n times}](http://s0.wp.com/latex.php?latex=%5Clg%28n%21%29+%3D+%5Clg%5CBig%5B+n+%5Ccdot+%28n+-+1%29+%5Ccdot+%28n-2%29+%5Ccdots+1%5CBig%5D+%5Cle+%5Clg+n+%2B+%5Clg+%28n-1%29+%5Ccdots+%5Clg1+%5Cle+%5Cunderbrace%7B%5Clg+n+%5Ccdots+%5Clg+n%7D_%5Ctext%7B+n+times%7D+&bg=ffffff&fg=333333&s=0 "\lg(n!) = \lg\Big[ n \cdot (n - 1) \cdot (n-2) \cdots 1\Big] \le \lg n + \lg (n-1) \cdots \lg1 \le \underbrace{\lg n \cdots \lg n}_\text{ n times}")
There are efficient algorithms that are able to sort of this complexity. For example, the merge sort has this complexity. Therefore, if you have an array of
that is, it takes about 20 million comparisons to sort an array of 1 million. Could we do any better than this? We can either upgrade the cpu of the machine doing the sorting or use two or more machines to divide the work among those machines. In this article, we are going to investigate the impact of dividing the work into smaller chunks and farming it to other processors.
Divide and Conquer
Assume we have an array 
This is also known as the MapReduce algorithm. Mapping is the process of assigning subsets of the input data to processors where each processor computes the partial result. Reducing is the process of aggregating the results of each processor to the final solution of the problem.
The process of merging is straightforward. Given two sorted arrays, begin by comparing the first element of each array. The smaller of the two will then occupy the first slot in the big array. The second element of the array from which we took the smallest element will now become the first element of that array. Repeat the process until all elements of both arrays have already occupied slots in the big array. The diagram below illustrates the algorithm of merging.
If you count the total number of comparisons that you need to merge two sorted arrays, you will find that it takes 
Since each processor has 
In our example, 
Can we do any better?
For a given value of 
In this diagram, we also plotted the horizontal line 
To get the value of
Simplifying,
Since this is a non-linear equation, we can solve this using the Newton's method. It is a method to compute the roots by approximation given an initial value of the solution. Starting from a guess solution 
where 
Substituting this to the formula for Newton's method, we get
Below is an R code using newton’s method to compute the root of the equation 
g=function(n,p){
p* 2^p - n
}
gprime=function(n,p){
p*2^p *log(2) - 2^p
}
newton=function(p,n,iter){
tmp = p
for(i in 1:iter){
p=p-g(n,p)/gprime(n,p)
if(abs(p-tmp)< 0.0001){
break
}
print(p)
tmp=p
}
print(p)
}
Running this code, we get the value of 
> newton(15,n,100) [1] 16.80905 [1] 16.08829 [1] 15.98603 [1] 16.00286 [1] 15.99944 [1] 16.00011 [1] 15.99998 [1] 16
Ignoring network latency, by distributing the input evenly into 16 processors, we get a running time of
In this age of multicore processors, parallel computing is fast becoming the norm than the exception. Learning to harness the power of multicores is becoming an extremely handy skill to have.
be the rate at which customers arrive, 
the rate at which customers places their order and also the rate at which they leave the second counter. Let us draw the markov chain diagram of this system.
. This is equal to the flow going out of state “00″ to state “10″: a*P00. Therefore,we have,
and 
. We can now solve for the probabilities by substituting these values to the above formula.
stocks can be computed.
. The time that elapses from the time the operator presses the submit button to the time it receives the response from the database as the response time 
. We can view the operators as alternating between two states namely “thinking” and “waiting” for response. Let 
be the average number of operators in “thinking” state and 
be the average number of operators “waiting” for response. Then since an operator can either be “thinking” or “waiting”, we have 
, where M is the number of operators.
is the number of completed transactions of resource 
and 
is the observation time.
and defined similarly as above:
is the number of transactions completed by the system.
. If a CPU takes on the average 30 msecs to complete a computation, then the service time for that type of transaction is 30 msecs.
, then the Utilization is defined as
,
:
is average time per transaction completed, which is precisely the service time. Therefore
. Then the total time a transaction spends on a resource 
where $S_i$ is the service time of resource 
of resource 
.
, as the utilization increase to 100%, the throughput also increases. However, when 
%, the throughput cannot be increased any further. Therefore, the throughput is bounded above by
.
. The service demand of the CPU is
be the probability of the system in state 1, 
be the probability of the system in state 2, etc. The quantity 
is called the flow of the system from state 1 to state 0, likewise, the quantity 
is the flow of the system out of state 0 to state 1. At steady state, these flows are equals
