Improving Fortran Do Loop Performance by 25%

SUMMARY

Here’s a way to make sure you’re optimizing the writing of your code with an example in Fortran. It’s a neat, non-obvious trick to an engineer, but may be more obvious to a computer scientist. It involves the writing of a do loop where you are updating your value for an array, and instead of copying that array into a temporary variable, you simply use the programming logic to continue to use that information (location in memory) during every other time step. I was able to get 25% better performance for this simple change (and it scales). Not clear yet? Let me show you.

BACKGROUND
I’m a mediocre Fortran programmer but I’m learning new tricks with practice, challenges, and going to professor office hours. Taking Scientific Computing and High Performance Computing Systems right now is really increasing the strength of my programming skills. I hope to be an intermediate Fortran programmer by the end of the semester. Below is a sample from a code I wrote for a recent class project. The goal of the project was not to write a sequential version, so I feel comfortable posting a piece of the serial version.

CODE DESCRIPTION

The user is stepping in time from igen to gmax, calculating the neighbor value (‘naybs’) of a cell in the array ‘pop.’ Then, it updates the value of the cell in the array ‘pop’ for the next time step based on the neighbor values. But it does this update in ‘buffer,’ unnecessarily copying the data back to the array ‘pop.’ In this way, the loop proceeds without conflict. This works, but you may be sacrificing performance without even realizing it. I wrote EXAMPLE 1 below and then my instructor said “BUT WHY NOT DO IT BETTER?” and I went back to my computer and coded EXAMPLE 2.

EXAMPLE 1: Original Code

  do igen = 1, gmax
    naybs = 0
    buffer = 0
! This loop finds neighbor values
    do j = 2, y_limit + 1
      do i = 2, x_limit +1
        naybs(i,j) = pop(i-1,j-1) + pop(i,j-1) + pop(i+1,j-1)+ &
                     pop(i-1,j  )              + pop(i+1,j  )+ &
                     pop(i-1,j+1) + pop(i,j+1) + pop(i+1,j+1)
        ! Birth
        if (pop(i,j)==0 .and. naybs(i,j)==3) then
            buffer(i,j)=1
        ! Survival
        else if (pop(i,j)==1 .and. &
            (naybs(i,j)==2 .or. naybs(i,j)==3)) then
            buffer(i,j)=1
        ! Death
        else
            buffer(i,j)=0
        end if
        pop(i,j) = buffer(i,j)
      end do
    end do
  end do

EXAMPLE 2: Improved Code

do igen = 1, gmax
  naybs = 0

  if (mod(igen,2)==1) then

! This loop finds neighbor values
  do j = 2, y_limit + 1
    do i = 2, x_limit +1
      naybs(i,j) = pop(i-1,j-1) + pop(i,j-1) + pop(i+1,j-1)+ &
                   pop(i-1,j  )              + pop(i+1,j  )+ &
                   pop(i-1,j+1) + pop(i,j+1) + pop(i+1,j+1)
      ! Birth
      if (pop(i,j)==0 .and. naybs(i,j)==3) then
          buffer(i,j)=1
      ! Survival
      else if (pop(i,j)==1 .and. &
          (naybs(i,j)==2 .or. naybs(i,j)==3)) then
          buffer(i,j)=1
      ! Death
      else
          buffer(i,j)=0
      end if
    end do
  end do

  else if (mod(igen,2)==0) then

! This loop finds neighbor values
  do j = 2, y_limit + 1
    do i = 2, x_limit +1
      naybs(i,j)=buffer(i-1,j-1)+buffer(i,j-1)+buffer(i+1,j-1)+ &
                 buffer(i-1,j  )              +buffer(i+1,j  )+ &
                 buffer(i-1,j+1)+buffer(i,j+1)+buffer(i+1,j+1)
      ! Birth
      if (buffer(i,j)==0 .and. naybs(i,j)==3) then
          pop(i,j)=1
      ! Survival
      else if (buffer(i,j)==1 .and. &
          (naybs(i,j)==2 .or. naybs(i,j)==3)) then
          pop(i,j)=1
      ! Death
      else
          pop(i,j)=0
      end if
    end do
  end do
  end if
end do

I will say that you do have to write more code, but if that’s your hang-up, then you might not be very interested in performance in the first place.

More importantly, note the logic here. What I’m doing is identifying which time step is odd or even (by computing the mod of each time step), and then based on that result, I will update the next time step with a value from another grid. As far as I know, this can be done more elegantly in C by switching pointers. I don’t even know how to yet use pointers effectively in Fortran, so that might be possible here too. That would then give you the performance you desire, and the brevity that everyone likes. This result did increase my performance by 25%, which is dramatic if you are in the scientific computing world.

I note that this may be obvious to others, and they might even think that I made it harder on myself in the first place by doing something silly (which I did), but remember that I was taught this by multiple people, multiple times. Once I started to get an understanding of how data is held in memory, I started to make more advanced strides in programming. Hope this helps!

Back to Engineering Graduate School: 10 must-haves

In this article I describe my favorite and must-have items for when I start my semesters in graduate school. A lot of what I list below can also be recommended for undergraduates.

  1. Computer
    Engineers require reliable tools. A computer is at the top of the list, whether you’re writing a technical report at the last minute, sharing gigabytes of files with your group project partners, or downloading a semester’s worth of lecture notes before an exam. These situations commonly arise during the semester and it is wise to find a dependable computer to help you avoid technological pitfalls. Personally, I enjoy having a powerful desktop at home, and a lightweight MacBook Air for the road. I recommend building a powerful desktop yourself. There are numerous video tutorials available on YouTube and written tutorials online. I update my desktop about once every 4 years and my laptop once every 3 years.
  2. Pen and Paper
    My favorite writing instrument is the Pilot Precise V5 Rolling Ball Pen, Extra Fine Point, 0.5 mm. While it will bleed through most poor quality papers, I make sure to purchase the National Brand Computation Notebook. I write on both sides to utilize up to 150 pages of notes for my classes. If my classes are powerpoint slide based, I still like to have the notebook for book notes or diagrams as supplements to my lectures.
  3. Folders and dividers
    An average engineering graduate class will have enough materials to fill up a 2 inch binder. I prefer Avery Heavy-Duty products to store my class materials. I also like to use Avery Big Tab Insertable Plastic Divider sets, which comes with 5 dividers. I typically divide my classes up into the following divider tab categories:
    – Handouts
    – Lectures
    – Homework
    – Exams
    – Work
    where handouts can be a syllabus or paper to read, and work can mean anything that I’ve scribbled or documented but did not submit, including messy homework assignments before I’ve re-written them in LaTeX.
  4. Software and storage
    You must back up your important research data on an external hard drive. I encourage backups of your backups if you have the resources. While hard drives usually seem inexpensive (considering our modern advances), you can get better deals during massive sale events like Black Friday. Very useful software tools for tracking your priorities include Evernote, Calendar, and OneNote.  I’ve also heard good things about OmniFocus and Workflowy. I agree that these tools are very useful but I find that they each have flaws, and a better tool is waiting to be developed.
  5. Mobile companion
    The modern graduate student is only as powerful as their mobile accessories. Apps for your smartphone can download an entire conference floorplan, including booth and activity information. Your Kindle or iPad can be used to read dozens of journal articles. You can know every detail about your life, including your personal finances, your email traffic, and communicate almost instantly with anyone in the world. Owning any combination of these devices is a must, but how you use them optimally is up to you.
  6. Electronics suite
    There is a long list of helpful electronics that you can buy to assist your graduate school efforts. I received a lot of help from Matt Might at his blog. He recommended several products that I tried. I swear by the Outlet To Go Power Strip and the Kensington presentation remote. I highly recommend car charger kits, USB hubs, iPod chargers, earbuds or headphones, ethernet adapter (if necessary), and a chill mat for when you’re at home on your laptop. High powered calculators are still a necessity for graduate students during exams, though they’re not as prominent as they were during undergraduate. Just keep your undergraduate calculator handy.
  7. Health care
    It’s important to stay healthy when in graduate school. I make sure I pack hand sanitizer, ibuprofen, allergy pills (Loratadine), Kleenex, and chewing gum in my bag. You can also boost your immune system by exercising. Try to get a running, biking, or swimming routine going. Also work on your muscle development during the week with a group fitness class at your University, if available. Play a sport or get involved in an intramural league. Take walks around campus when you can as it will keep your brain healthy.
  8. Parking pass
    Transportation departments at campuses across America are not always in the favor of the students. Lots of parking tickets are ruthlessly handed out each semester. My advice is to obey the posted signs and stop complaining. Buy a parking pass if it is financially feasible, or consider an alternative mode of transportation to work. I highly emphasize that there are many programs available to students for green commuting and there may be subsidies for your form of travel (whether biking, bus, or carpool).
  9. Office Mates
    It surprises me how often my friends borrow a stapler, a hole punch, scissors, or all three at the same time. I have a very strong stapler and hole punch, and average scissors for my office. I recommend staplers and hole punches that can power through up to 50 pages at once. This industrial level action may come in handy when your pocket stapler cannot handle a 30 page report.
  10. Memento
    Keep something motivational in your office. Whether it’s a poster of your favorite poem, a die-cast model of your favorite plane, or a picture of you with your hero, you will benefit from being reminded of why you are a graduate student in the first place. Your perspective will frequently change during graduate school. There will be lots of ups and downs. Just remember why you’re here.