Mastering IPython 4.0

Early languages were generally not very human-friendly. It took specialized training to be able to write (and read) programs written in these languages. Programmers would often add comments to their code, either within the code itself or in external documentation, but the problem was deeper. The languages themselves were cryptic.

For example, the following code in x86 assembly language determines whether a year is a leap year or not (from http://rosettacode.org/wiki/Leap_year#X86_Assembly):

    align 16
; Input year as signed dword in EAX
IsLeapYear:
    test eax,11b
    jz .4
    retn ; 75% : ZF=0, not a leap year
.4:
    mov ecx,100
    cdq
    idiv ecx
    test edx,edx
    jz .100
    cmp edx,edx
    retn ; 24% : ZF=1, leap year
.100:
    test eax,11b
    retn ; 1% : ZF=?, leap year if EAX%400=0

This is the first problem Fortran addressed. Fortran set out to be more readable. An important goal was that mathematical equations in code should look like mathematical expressions written by human beings. This was an important step in enabling coders to express algorithms in terms that they themselves understood, as opposed to a format the machine could directly work with. By comparison, a Fortran function to determine whether a year is a leap year reads easily (from http://rosettacode.org/wiki/Leap_year#Fortran):

pure elemental function leap_year(y) result(is_leap)
  implicit none
  logical :: is_leap
  integer,intent(in) :: y

  is_leap = (mod(y,4)==0 .and. .not. mod(y,100)==0) .or. (mod(y,400)==0)

end function leap_year

The first languages were specific to the machine they were meant to run on. A program written on one machine would not run on another. This led to the wheel being reinvented often. Consider a sorting algorithm. Many programs need to sort their data, so sorting algorithms would be needed on many different computers. Unfortunately, an implementation of quicksort on one machine, in that machine's language, would not run on another machine, in its language. This resulted in many, many reimplementations of the same algorithm.

Also, a programmer who knew how to write code on one machine had to relearn everything to use another. Not only was it difficult for talented individuals to go where they were needed, but also buying a new machine meant retraining the entire staff. The first thing the staff then did was rewrite all the existing (working) code so that it would run on the new machine. It was a tremendous waste of talent and time.

This is the second problem Fortran addressed—how can a program be expressed so that it runs on more than one machine (that is, how can programs be made portable)? The goal was that if a program was written in Fortran on one machine, then it would run on any other machine that supported Fortran.

To this end, Fortran compilers were developed. A compiler translates a program in one language (Fortran in this case) to another language (the language of the machine the program would run on).

While readability and portability were important, no one was going to use Fortran if the resulting program ran slowly on their computer. Early coders expended immense amounts of time and effort making their code run as quickly as possible. Problems were big and computers were slow and time was money.

This is the third problem Fortran addressed—and its solution—is the primary reason Fortran is still in use today: Fortran programs run fast. The details are out of the scope of this book but the result is clear. Algorithms expressed in Fortran run quickly. Fortran was designed that way. Implementations are judged on their efficiency, compilers generate clean code, and coders always have an eye on performance. Other languages have surpassed it in terms of readability, portability, and other measures of quality, but it is a rare language that measures up in terms of efficiency.

It is important to understand some of the environment that Fortran programs were running in when it was first developed. While we are used to a computer running multiple programs simultaneously today (multitasking), early computers ran only one program at a time. The programs would sit in a queue, in order. The operating system would take the first program, run it from beginning to end, then do the same for the next program, and so on. This form of job scheduling is known as a batch system.

Batch systems are very efficient. At the very bottom of things, a processor can only do one thing at a time. A multitasking system just switches what the processor is doing from one thing to another very quickly, so it looks like multiple things are happening at once. This makes for a smoother user experience; however, multitasking systems can spend a lot of time doing this switching.

Batch systems can devote this switching time to running the program. In the end, the program runs faster (although the user experience is degraded). Fortran, with its emphasis on speed, was a natural fit for batch systems.

Many of the benefits and drawbacks of Fortran are linked to its longevity. For the kinds of things that have not changed over the decades, Fortran excels (for example, numerical computing, which is what the language was originally designed for). Newer developments (for example, text processing, objects) have been added to the language in its various revisions.

The benefits of Fortran are as follows:

The drawbacks of Fortran are as follows:

IPython/Python is the new kid in town. It began in 2001 when Fernando Perez decided that he wanted some additional features out of Python. In particular, he wanted a more powerful command line and integration with a lab-notebook-style interface. The end result was a development environment that placed greater emphasis on ongoing interaction with the system than what traditional batch processing provided.

The nearly 45-year delay between the advent of Fortran and IPython's birth provided IPython the advantage of being able to natively incorporate ideas about programming that have arisen since Fortran was created (for example, object-orientation and sophisticated data structuring operations). However, its relative newness puts it behind in terms of installed code base and libraries. IPython, as an extension of Python, shares its benefits and drawbacks to a large extent.

The benefits of IPython are as follows:

The drawbacks of IPython are as follows:

Some of these benefits deserve more extensive treatment here, while others merit entire chapters.

Ease of adoption

It is easy to learn Python. It is currently the most popular introductory programming language in the United States among the top 39 departments (http://cacm.acm.org/blogs/blog-cacm/176450-python-is-now-the-most-popular-introductory-teaching-language-at-top-us-universities/fulltext):

Note that Fortran is not on the list.

This is no accident, nor is Python limited to a "teaching language." Rather, it is a well-designed language with an easy-to-learn syntax and a gentle learning curve. It is much easier to learn Python than Fortran, and it is also easier to move from Fortran to Python than the reverse. This has led to an increasing use of Python in many areas.

The trend toward teaching Python has meant that there is a much larger pool of potential developers who know Python. This is an important consideration when staffing a project.

TIOBE Software ranks the popularity of programming languages based on skilled engineers, courses, and third-party vendors. Their rankings for October 2015 put Python in the fifth place and growing. Fortran is 22nd (behind COBOL, which is 21st).

IEEE uses its own methods, and they produced the following graph:

The column on the left is the 2015 ranking, and the column on the right is the 2014 ranking, for comparison. Fortran came in 29th, with a Spectrum ranking of 39.5.

If developers were all equal in talent, they worked for free, development time were no object, all code were bug-free, and all programs only needed to run once and were then thrown away, Fortran would be the clear winner given its efficiency and installed library base.

This is not how commercial software is developed. At a first approximation, a software project's cost can be broken down into the cost of several parts:

There are alternatives to the stark IPython/Fortran choice: cross-language development and prototyping.

Rosetta Code (http://rosettacode.org/wiki/Rosetta_Code) is an excellent site that contains solutions to many problems in different programming languages. Although there is no guarantee that the code samples contained on the site are optimal (in whatever sense the word "optimal" is being used), its goal is to present a solution usable by visitors who are learning a new language. As such, the code is generally clear and well-organized. The following examples are from the site. All code is covered under the GNU Free Documentation License 1.2.

module fft_mod
  implicit none
  integer,       parameter :: dp=selected_real_kind(15,300)
  real(kind=dp), parameter :: pi=3.141592653589793238460_dp
contains

  ! In place Cooley-Tukey FFT
  recursive subroutine fft(x)
    complex(kind=dp), dimension(:), intent(inout)  :: x
    complex(kind=dp)                               :: t
    integer                                        :: N
    integer                                        :: i
    complex(kind=dp), dimension(:), allocatable    :: even, odd

    N=size(x)

    if(N .le. 1) return

    allocate(odd((N+1)/2))
    allocate(even(N/2))

    ! divide
    odd =x(1:N:2)
    even=x(2:N:2)

    ! conquer
    call fft(odd)
    call fft(even)

    ! combine
    do i=1,N/2
       t=exp(cmplx(0.0_dp,-2.0_dp*pi*real(i-1,dp)/real(N,dp),kind=dp))*even(i)
       x(i)     = odd(i) + t
       x(i+N/2) = odd(i) - t
    end do

    deallocate(odd)
    deallocate(even)

  end subroutine fft

end module fft_mod

program test
  use fft_mod
  implicit none
  complex(kind=dp), dimension(8) :: data = (/1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0/)
  integer :: i

  call fft(data)

  do i=1,8
     write(*,'("(", F20.15, ",", F20.15, "i )")') data(i)
  end do

end program test

from cmath import exp, pi

def fft(x):
    N = len(x)
    if N <= 1: return x
    even = fft(x[0::2])
    odd =  fft(x[1::2])
    T= [exp(-2j*pi*k/N)*odd[k] for k in xrange(N/2)]
    return [even[k] + T[k] for k in xrange(N/2)] + \
           [even[k] - T[k] for k in xrange(N/2)]

print( ' '.join("%5.3f" % abs(f)
for f in fft([1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0])) )

It would be difficult to compare the performance of these programs. The time required to run a program can be influenced by many things outside of the inherent properties of the language:

The question of how fast code runs is independent of the question of how long it takes to write, debug, and maintain. It is notoriously difficult to estimate how much time / how much effort will be required to write a program before the development has started. This uncertainty remains throughout the development cycle, with many projects going well over time and budget. Even when coding is complete, it can be difficult to tell how efficient the entire process was. A means to measure effort would help answer these questions.

There are two primary ways to measure the amount of effort required to write software, mentioned as follows.

In the past, most HPC and parallel programming were done on a limited number of expensive machines. As such, the most important criteria by which programs were measured was execution speed. Fortran was an excellent solution to the problems of writing fast, efficient programs. This environment was acceptable to the community, which needed to perform these types of calculations, and it gradually separated from mainstream commercial computing, which developed other concerns.

The birth of cloud computing (and cheaper hardware in general) and the evolution of big data has caused some in the commercial mainstream to reconsider using large, parallel systems. This reconsideration has brought commercial concerns to the fore: development and maintenance costs, testing, training, and other things. In this environment, some (small) trade-off in speed is worth it for significant gains in other areas. Python/IPython has demonstrated that it can provide these gains with a minimal runtime performance cost.

This was a satisfactory relationship for some time. The types of problems of interest to the HPC community (complicated physical modeling and advanced mathematics) had little overlap with the rest of computer science. HPC was a niche with a very high barrier to entry. After all, there were just not that many massively parallel computers to go around.

In a sense then, programming HPC systems was an island. On the island, there were ongoing research programs centered on important HPC-centric questions. Tools were built, skills were developed, and a community of practice developed to the point that approaching HPC from the outside could be daunting. Advances occurred outside of HPC also, but those inside it had their own concerns.

As time passed, the HPC island drifted further and further from mainstream computing. New areas opened up: web computing, mobile computing, agile methods, and many others. HPC took what it needed from these areas, but nothing really affected it. Until something finally did…

Amazon had a problem. During the Christmas season, it used a lot of computer power. For the rest of the year, these computers would sit idle. If there were some way to allow people to rent time on these idle machines, Amazon could make money. The result was an API that allowed people to store data on those machines (the Amazon Simple Storage Service, or S3) and an API that allowed people to run programs on the same machines (the Amazon Elastic Compute Cloud, or EC2). Together, these made up the start of the Amazon Cloud.

While not the first system to rent out excess capacity (CompuServe started off the same way several decades earlier), Amazon Cloud was the first large-scale system that provided the general public paid access to virtually unlimited storage and computing power.

It is not clear whether anybody realized what this meant at first. There are a lot of uses of clouds—overflow capacity, mass data storage, and redundancy, among others—that have a wide appeal. For our purposes, the cloud meant one thing: now everybody has access to a supercomputer. HPC will never be the same again.

The current relationship between HPC and highly parallel architectures is relatively new. It was only in the 1990s that HPC left the realm of very fast single-processor machines for massively parallel architectures. In one sense, this was unfortunate, as the old Cray machines were aesthetic marvels:

The image is taken from a public domain: https://commons.wikimedia.org/wiki/File:Cray2.jpeg

It was largely inevitable, however, as single-processor systems were bumping up against physical limitations involving transistor density and cooling.

The change in architecture did not bring with it a change in the problems to be solved. To this end, the generic supercomputer physical architecture evolved toward:

Moving from single to multiple processors brought issues with locality. Every time a program running on one processor needed data from another processor (or disk), processing could come to a halt as the data was being retrieved. The physical architecture of the supercomputer is meant to minimize the latency associated with non-local data access.

Given the position of HPC centers as early adopters of parallel architectures, "parallel programming" came to be largely synonymous with "HPC programming." This is largely a historical accident, and new paradigms have opened up parallel computing to constituencies outside of the HPC world. As such, this book will use the two terms interchangeably.

We now turn to one of the new paradigms, cloud computing, and discuss its similarities and differences from standard HPC.

There are some differences between a "real" supercomputer and what most clouds offer. In particular, a cloud's physical architecture will contain:

In addition, clouds are generally heterogeneous and easily scaled. While an initial cloud is likely to have many subsystems with the same processor, RAM, hard drives, and so on, over time new subsystems will be added, with newer (or at least different) technology. The loose coupling of cloud systems encourages this sort of organic growth.

Differences in architecture mean that some algorithms will run well on supercomputers versus others that favor clouds. A lot of software that runs on supercomputers will not run on clouds; period (and vice versa)! This is not always just a matter of recompiling for a new target platform or using different libraries. The underlying algorithm may not be suited for a particular paradigm.

If speed is imperative and you have the budget, there is still no substitute for a special-purpose HPC system. If cost, ease of access, redundancy, and massive parallelism are desired, a cloud fits the bill.

That is not to say the two worlds (HPC and cloud) are completely distinct. Despite these architectural differences, it is worth noting that an Amazon EC2 C3 instance cluster is listed at 134 on the top 500 list of fastest HPC systems as of June 2015. Even on HPC's own terms, cloud computers offer respectable performance.

The core audience for this book then consists of members of both of these groups:

Each group has the skills the other wants. HPC programmers understand scientific computing, efficiency, and parallelism. Python programmers are skilled in interactivity, usability, correctness, powerful development tools, ease of debugging, and other capabilities that mainstream computing values. New technology means that future systems will need to incorporate elements from both skill sets.

Wall-clock time is the amount of time that passes from the beginning of execution of a program to the end of its execution, as measured by looking at a clock on the wall. Wall-clock time is the measure people usually care about.

Cycle time is the time obtained by summing up the number of cycles taken by the program during its execution. For example, if a CPU is running at 1 MHz, each cycle takes 0.000001 seconds. So if it takes 2,500,000 cycles for a program to run, then it means the program took up 2.5 seconds of cycle time.

In a batch system with a single processor, the times are always the same. In a multitasking system, wall-clock time is often longer than cycle-time as the program may spend wall-clock time waiting to run without using any cycles.

With more than one processor, comparing the two times for an algorithm became more complicated. While not always true, many programs could be divided into pieces, such that running the program on two or more processors simultaneously reduced the wall-clock time, even if the cycle-time went up. Since wall-clock time is the important measure, for these algorithms, the answer was "Yes."

One can quantify this effect as follows:

In general, when using a batch system:

There are some algorithms for which . These are known as embarrassingly parallel algorithms. In this case, adding more processors results in linear speedup, which is where machines with many processors really shine.

In summary, the answer to the question, "Are more processors better?" is that it depends on the algorithm. Luckily for parallel computing, many algorithms show some amount of speedup and many important problems can be solved using these algorithms.

Consider the Collatz conjecture. Given the following function:

The conjecture is: for any positive integer, repeated application of f(n) will always reach the number 1. It is believed that the conjecture is true, but there is currently no proof. We are concerned with how long it takes to reach 1, that is, how many applications of f(n) are required for a given n. We would like to find the average for all n, 1 to 100.

The term for the sequence of numbers generated for any n is hailstone sequence. For example, the hailstone sequence for n = 6 is 6, 3, 10, 5, 16, 8, 4, 2, 1. We are interested in the average length of hailstone sequences.

A serial program

A regular (serial) Python program for computing the answer might look as follows:

def f(n):
    curr = n
    tmp = 1
    while curr != 1:
        tmp = tmp + 1
        if curr % 2 == 1:
            curr = 3 * curr + 1
        else:
            curr = curr/2
    return tmp

def main( ):
    sum = 0
    for i in range(1, 101):
        sum = sum + f(i)
    avg = sum / 100.0

Tip

Detailed steps to download the code bundle are mentioned in the Preface of this book. Please have a look.

The code bundle for the book is also hosted on GitHub at https://github.com/PacktPublishing/Mastering-IPython-4. We also have other code bundles from our rich catalog of books and videos available at https://github.com/PacktPublishing/. Check them out!

A schematic of the processing would look like this:

Without going into too much detail, it is easy to see that the running time of the preceding program can be expressed as:

• Setup (definition of f, initialization of sum, and so on)

• Loop body (the sum of the amount of time to compute 100 hailstone sequences one at a time)

• Teardown (calculate the average)

It is obvious that the running time of the program will be dominated by one of the loops. There is not much to be done about the while loop inside of f. Each iteration after the first depends on the result of a previous iteration. There is no way to, for example, do the tenth iteration without having already done the ninth, eighth, and so on.

The for loop inside of main has more potential for parallelization. In this case, every iteration is independent. That is:

• Each iteration computes its own value, (f(i))

• The computation of each f(i) does not depend on any other iteration

• The values can easily be combined (via summation)

This algorithm can be converted to a parallel equivalent with a few extra commands. As they stand, these functions are pseudo-code—equivalent IPython functions will be described in later chapters:

• getProcs(num): Returns a list of num processors

• proc.setFun(fun, arg): Assigns a function fun with an argument arg to the proc processor

• procs.executeAll( ): Executes fun on all processors in proc in parallel

• proc.fetchValue( ): Returns the value computed on the proc processor when the calculation is complete

A parallel equivalent

With these additions, a parallel equivalent might look as follows:

def f(n):
    curr = n
    tmp = 1
    while curr != 1:
        tmp = tmp + 1
        if curr % 2 == 1:
            curr = 3 * curr + 1
        else:
            curr = curr/2
    return tmp

def main( ):
    sum = 0
    procs = getProcs(100)
    i = 1

    for proc in procs:
        proc.setFun(f, i)
        i = i + 1

    procs.executeAll( )

    for proc in procs:
        sum = sum + proc.fetchValue( )

    avg = sum / 100.0

A schematic of the processing would look as follows:

Discussion

While the parallel version is slightly longer (20 lines of code compared to 15), it is also faster, given enough processors. The intuitive reason is that the invocations of f are not queued up waiting for a single processor. With a single processor, the invocation of f(i) has to wait in line behind all the previous invocations of f(a) where 1 ≤ a < i, even though there is no dependency between them. The single processor is an unnecessary bottleneck. In this case, as no call to f depends on any other call, this algorithm is embarrassingly parallel.

When a series of functions calls, (f1, f2, …, fn), is queued up for an algorithm A, it is easy to see that the cycle time required to complete all n function calls is:

In the embarrassingly parallel case, the cycle time becomes (potentially) much smaller:

This results in a speedup (ignoring setup and teardown) of:

In the case where all fi use the same number of cycles, this simplifies to the following:

Several issues important to parallel programming have been glossed over in the preceding discussion. These issues are important enough to have all of Chapter 3, Stepping Up to IPython for Parallel Computing, devoted to them.