tag:blogger.com,1999:blog-48900397220031273412024-03-27T19:53:20.300-04:00Prof. Douglas ThainReflections on distributed computing in clusters, clouds, and grids.Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.comBlogger43125tag:blogger.com,1999:blog-4890039722003127341.post-56681697381773570432020-02-24T17:18:00.000-05:002020-02-25T13:32:30.751-05:00Getting Beyond Stack Overflow for CS StudentsQuestion and answer sites like Stack Overflow (and similar Q&A sites) have become a valuable resource for programmers struggling with tricky problems. However, I have noticed that Q&A sites can become a "trap" for students learning how to program. You can get stuck for a long time searching for a question that doesn't quite address your question.<br />
<br />
The problem is that Q&A sites are oriented toward solving <i>very specific </i>questions, rather than developing a <i>general understanding</i> of a technology. If a post answers the very specific question that you have, that's nice, but it doesn't necessarily help you to develop your own solution to other problems. What's worse, the answers are sometimes incorrect, or not applicable to the situation that you actually have. <br />
<br />
Here is a classic train wreck with thousands of votes: <a href="https://stackoverflow.com/questions/46155/how-to-validate-an-email-address-in-javascript">How to validate an email address in JavaScript?</a> One can assume the poster is looking for a quick one liner to solve this problem. The problem is that the question is not sufficiently well formed. How does one define an email address? Do you want to be conservative or flexible? What does it mean to "validate" anyhow? Some of the answers posted provide colossal regular expressions, but unless you understand regular expressions, you won't know if they work correctly. (Some of the solutions don't actually work.)<br />
<br />
If you intend to be a professional who <i>solves problems for people</i>, you need to be able to think through these issues yourself, rather than just copy-pasting a solution. In the case of validating email addresses, that means learning how regular expressions work from first principles, and then thinking carefully about what problem you really intend to solve.<br />
<br />
Now, I can't prohibit anyone from looking on Stack Overflow, nor will I try. But I would like to suggest some different habits of learning that will lead to more fulfilling results and less frustration. And, it will help you to become the sort of person who <i>answers</i> questions on Q&A sites.<br />
<h2>
</h2>
<h2>
An Approach To Solving Programming Problems</h2>
<div>
<ol>
<li>Learn the atoms that make up your system.</li>
<li>Experiment by combining them in simple ways.</li>
<li>Solve your actual problem gradually by building up complexity.</li>
</ol>
</div>
<h3>
</h3>
<h3>
Learn the Atoms</h3>
<div>
Every layer of a computer system is an abstraction that is made up of some fundamental set of basic operations, which I'll just call <i>atoms</i>. Each atom manipulates the system in some particular and well-documented way.</div>
<ul>
<li>If you are learning how to manage processes in Unix, then your atoms are system calls like <a href="http://man7.org/linux/man-pages/man2/fork.2.html">fork</a>, <a href="http://linux.die.net/man/3/exec">exec</a>, <a href="https://linux.die.net/man/2/wait">wait</a>, <a href="https://linux.die.net/man/2/kill">kill</a>, and <a href="https://linux.die.net/man/2/exit">exit</a></li>
<li>If you are learning <a href="https://docs.python.org/3/library/re.html">regular expressions</a>, then your atoms are concatenation (xy), alternation (x|y, closure (x*), and so forth.</li>
<li>If you are learning how to render graphics in <a href="https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/">OpenGL</a>, then your atoms are these functions like <a href="https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glBegin.xml">glBegin</a>, <a href="https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glVertex.xml">glVertex</a>, <a href="https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glColor.xml">glColor</a>, and <a href="https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glEnd.xml">glEnd</a>.</li>
<li>If you are learning <a href="https://www3.nd.edu/~dthain/compilerbook/chapter10.pdf">X86 assembly language</a>, then your atoms are instructions like MOV, ADD, SUB, CMP, and JMP.</li>
</ul>
Sometimes just figuring out what the atoms are can be tricky. This is where a good introductory guide or textbook is helpful. Without giving you every last detail of the atom, an introductory guide tells you the set of atoms needed to get started and their general relationship. (This is probably the most important thing teachers do in the classroom: help you to understand the atoms of a system.)<br />
<div>
<br /></div>
<div>
Once you know what the atoms are, then you need to learn how they work in detail. This is going to require some effort on your part. Find the reference manuals for those atoms and read them. If it has a man page, read it. Yes, really read it, I'm not kidding. You ought to be able to easily summarize the purpose of each atom from memory, and look up the details when necessary.</div>
<div>
<br /></div>
<div>
A really elegant system design (e.g. Unix or LISP) will have only a handful of atoms. (That's what makes it elegant.) A not-so-elegant system (e.g. Win32) may have hundreds, and so you can't learn it all up front. In that case, you have to pick a few atoms that appear to work together, and proceed to the next step.</div>
<h3>
</h3>
<h3>
Experiment by Combining Things</h3>
<div>
Now that you understand some of the atoms, start to combine them together in simple ways and test them out. Don't even try to solve your initial problem yet, just try a few things at small scale.</div>
<div>
For example, suppose you are learning Unix process management, and you think you have a basic understanding of the fork system call. Begin by writing the smallest program that does something, perhaps this:</div>
<br />
<blockquote class="tr_bq">
<span style="font-family: "courier new" , "courier" , monospace;">pid_t pid = fork();<br />printf("hello from pid %d\n",getpid());
</span></blockquote>
<br />
Now, test your understanding by making a prediction. What do you think this program will output? Ok, now run it. Did it output what you expect? Great, continue. If not, then go back and re-read the behavior of fork to see where you misunderstood it.<br />
<div>
<br /></div>
<div>
If that worked, then add one more atom and see what happens. Maybe you try this:</div>
<div>
<br /></div>
<blockquote class="tr_bq">
<div>
<span style="font-family: "courier new" , "courier" , monospace;">pid_t pid = fork();<br />execlp("/bin/ls","ls",0);</span></div>
</blockquote>
<div>
<br /></div>
<div>
Again, make a prediction: what do you think this will output? Test your prediction. Did you get it right? Ok, add a little more:</div>
<div>
<br /></div>
<blockquote class="tr_bq">
<div>
<div>
<span style="font-family: "courier new" , "courier" , monospace;">pid_t pid = fork();<br />if(pid==0) {<br /> execlp("/bin/ls","ls",0);<br />}<br />printf("created child %d\n",pid);</span></div>
</div>
</blockquote>
<div>
<br /></div>
<div>
As you add complexity to your examples, start to think about undesired situations and edge cases. For example, what happens if you attempt to execute a program that doesn't exist? Change your little example to test that possibility, and predict its output:</div>
<div>
<br /></div>
<blockquote class="tr_bq">
<div>
<div>
<span style="font-family: "courier new" , "courier" , monospace;">pid_t pid = fork();<br />if(pid==0) {<br /> execlp(<b>"/bin/junk"</b>,"ls",0);<br />}<br />printf("created child %d\n",pid);</span></div>
</div>
</blockquote>
<div>
<br /></div>
<div>
Hmm, that probably didn't have the desired effect. Can you explain what happened? You will have to add a little bit more code to handle the possibility of <span style="font-family: "courier new" , "courier" , monospace;">execlp()</span> failing. Take a look at your atoms and see which one makes sense.</div>
<div>
<br /></div>
<div>
As you go on, you will gain confidence in your understanding of the atoms that make up the system, and you will be able to focus more on the structure of programs that use the atoms, rather than stumbling over how they work individually.</div>
<h3>
</h3>
<h3>
Solve Your Actual Problem Gradually</h3>
<div>
After spending some time working out the atoms and simple combinations, you are ready to come back to your initial problem. With the details of each atom clearly in your head, you can rely less on internet searches and online manuals, and more on using your own brainpower to make new combinations. Suppose you are given the following goal:<br />
<i><br /></i>
<i>Your company has an important service that needs to be running continuously, except it has a habit of crashing every 30 seconds or so. Your boss asks you to write a "watchdog" program that keeps four copies of the service running all the time. Whenever any instance of the server crashes or exits, the watchdog should restart it.</i><br />
<br />
There is no answer to this specific question on Stack Overflow, so you are going to have to figure it out for yourself. If the solution doesn't jump out at you, do not despair. Try solving a simpler problem first, and then approach the full problem by adding complexity gradually. For example, you could write four versions of the solution like this:<br />
<br />
<ul>
<li>Version 1: Run one instance of the service and wait for it to finish.</li>
<li>Version 2: Run four instances of the service sequentially, starting one as soon as the previous as finished.</li>
<li>Version 3: Run four instances of the server in parallel, and wait until all of them have finished.</li>
<li>Version 4: Run four instances of the service continuously, so that as soon as one of the four exits, another one is started.</li>
</ul>
<br />
As you go along, you may find that you have forgotten a detail about one of your atoms. That's fine, go back to the manual and look it up again. Perhaps you encounter a very strange error message that is not mentioned in the manual. That's a great item to search for on the internet. But if you understand your atoms well, most of your mental energy can be focused on combining them into a coherent whole.<br />
<br /></div>
Douglas Thainhttp://www.blogger.com/profile/12930374395317667662noreply@blogger.com5tag:blogger.com,1999:blog-4890039722003127341.post-35798131444680408182018-10-08T15:19:00.002-04:002018-10-08T15:54:01.614-04:00Compilers Book, First EditionI am happy to announce that the first edition of "Introduction to Compilers and Language Design" is now available at <a href="http://compilerbook.org/">http://compilerbook.org</a>. This is a free online textbook: you can access the PDFs directly, or order an inexpensive hardcover book.<br />
<br />
Thank you to all the students who previewed this book and fixed typos
and other errata. Thanks especially to Andrew Litteken, who drafted
and tested the chapter on ARM assembly.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://www3.nd.edu/~dthain/compilerbook/frontcover.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="800" data-original-width="526" height="200" src="https://www3.nd.edu/~dthain/compilerbook/frontcover.png" width="131" /></a></div>
Douglas Thain,<br />
<b>Introduction to Compilers and Language Design</b>,<br />
1st edition, 2018.<br />
<a href="http://compilerbook.org/">http://compilerbook.org</a><br />
Hardcover ISBN: 978-0-359-13804-3<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
I first estimated the book would be finished in 2017, but it took another semester to finalize several chapters, while also teaching a different class!<br />
<br />
Finally, I should mention that I was inspired by Andrea and Remzi Arpaci-Dusseau, who set a fine example by publishing <a href="http://ostep.org/">Operating Systems in Three Easy Pieces</a> as a free online textbook.<br />
<br />
<br />Douglas Thainhttp://www.blogger.com/profile/12930374395317667662noreply@blogger.com1tag:blogger.com,1999:blog-4890039722003127341.post-56992622828466967092018-05-21T10:36:00.000-04:002018-05-21T10:38:06.939-04:00Graduation Address for Catholic Engineers<i>I had the pleasure of speaking at the commencement ceremony for the Department of Computer Science and Engineering at the University of Notre Dame in 2018. Here is what I wrote:</i><br />
<i></i><br />
<br />
Good afternoon!<br />
<br />
It is a real pleasure to see all of these young men and women dressed up so nicely. As you may know, I spent a semester with all of the CSE students here as juniors in operating systems, compilers, and some other classes as well. It was rather early in the morning, and so as often as not, they were dressed in pajamas, flip-flops, and sometimes sweaty gym clothes. It is lovely to see everyone at their best.<br />
<br />
I invite you all to just relax for a little while, look around you, and take in this moment. Reflect a bit on the path that led you here.<br />
<br />
I'm sure that for most of you, it seems like you just arrived! Perhaps you took a long road trip to South Bend, and unloaded the car on a sweaty August afternoon. You met your roommate and probably wondered about their peculiar taste in music or food. You found your way around campus, met some interesting professors, did a lot of homework, and probably slept through a lecture once in a while. I'm sure every one of you has had moments of triumph, and some of tears as well. I hope that you made some lifelong friends, and maybe found romance along the way as well.<br />
<br />
But of course, the reason that you came to Notre Dame was to struggle with the timeless questions that scholars have asked throughout the ages:<br />
<ul>
<li>What is free will, and do humans really have it?</li>
<li>Are we redeemed by our faith, by works, or by the grace of God?</li>
<li>What is the meaning of "segmentation fault"?</li>
<li>Why does "git pull" default to merging instead of rebasing?</li>
</ul>
As pleasant as it is to look back upon the college years, I am here to tell you that this is not the end, but only the beginning. The world needs your talents, and you have a lot of important work ahead of you.<br />
<br />
The modern world needs engineers, and our moment in time particularly needs Catholic engineers. To that end, I would like to offer a little reflection on the personal motto of Bishop Rhoades, which is "Veritatem in Caritate" or "Truth in Charity" This is an excellent motto for an engineer to keep in mind.<br />
<br />
Truth in Charity: You cannot speak the truth effectively unless you speak with charity. Likewise, it makes no sense to speak with charity if what you say is not the truth.<br />
<br />
First, truth. Our society is currently undergoing a loss of confidence in the idea of truth itself. Senator Daniel Patrick Moynihan once said, "Everyone is entitled to their own opinion, but not their own facts." and this was often repeated as a sensible guideline for political debate. Today, we are finding it more and more difficult to agree on the basic facts of a situation. And there is no point debating our opinions without first having facts: What was the high temperature today? Which car is more fuel efficient? How many people in Indiana are unemployed?<br />
<br />
The wonder of the Internet is that it has enabled everyone access to the world's knowledge, and allowed everyone to have a voice, which is empowering. But it has become harder for the average person to distinguish between trustworthy information and outright fabrications. I just took a look at the fact-checking site snopes.com, which felt it was necessary to debunk the myth that it is common for ostriches to go downhill skiing in Japan!<br />
<br />
But an engineer deals with physical reality and knows that the truth exists, whether we like it or not. Nature cannot be cheated. A drone that runs out of battery will fall out of the sky. A program with a race condition will lock up. A circuit that draws too much power will catch fire. An engineer's job is to stand up for the truth -- however inconvenient it may be -- because they know that Nature will come to settle the account sooner or later.<br />
<br />
Second, charity. It's no secret that our society is short on charity, which is a concern for the well-being of our neighbors. You all know the headlines about things like subprime mortgages, cheating on emissions tests, and the sale of personal data. In these and many more cases, clever people used their talents to benefit themselves while exacting a price not just against their immediate victims, but on society as a whole. Volkswagen might be able to pay back car owners who were defrauded, but there is nothing it can do to extract the excess pollution from the atmosphere.<br />
<br />
As engineers, you will build the machines that make society operate. In the twentieth century, that meant things like locomotives and roads and bridges. In the twenty-first century, it includes search engines, voting machines, and self-driving cars. In every single one of these cases, yes, there is a customer to satisfy, but society at large a greater interest to be protected.<br />
<br />
And so, as engineers, I charge you to <b>speak the truth in charity</b>:<br />
<br />
Some of you may work on self-driving cars, which have the potential to reduce crashes and save time and money. But when a self-driving car has a flaw that threatens pedestrians, who will speak the truth in charity? You will!<br />
<br />
Some of you may work on artificial intelligence, which enables us to find hidden patterns in massive datasets. But when a neural network perpetuates racism because of its poorly chosen training data, who will speak the truth in charity? You will!<br />
<br />
Some of you may work on systems for digital voting, which can make it easier for every citizen to participate in the political process. But when a voting system with a security flaw puts our democracy at risk, who will speak the truth in charity? You will!<br />
<br />
Now, perhaps that is all a bit heavy for this moment. It's a <strike>beautiful</strike> (rainy) spring day, you have worked hard to be here, and it's time to celebrate. So, let me instead give you one piece of advice that is more immediate. You can put it into use today!<br />
<br />
It is all too easy to get attached to our phones, our computers, our gadgets, and get sucked into the endless chatter of status updates, news items, upvotes, comments, and so forth. These constant distractions can prevent us from having deeper experiences with other people, and draw us away from truth and charity.<br />
<br />
Take time every day to turn off your gadgets. Enjoy a meal without looking at your phone. Spend an evening without the TV. Take a walk without looking at your watch. Trust me, your friends, your spouse, your children, and your parents will be much happier with your full attention.
You can start at dinner with your family tonight: whoever picks up their phone first during dinner pays the bilk!<br />
<br />
It has been a pleasure to have you here at Notre Dame.<br />
<br />
Congratulations and good luck!<br />
<br />
Don't forget to brush your teeth.Douglas Thainhttp://www.blogger.com/profile/12930374395317667662noreply@blogger.com1tag:blogger.com,1999:blog-4890039722003127341.post-73436214569397843062017-12-04T15:42:00.001-05:002017-12-04T16:56:03.260-05:00Build a Compiler for AlbaCore in Spring 2018Profs. Brockman and Thain are currently recruiting multiple undergraduate students to participate in a spring project at the intersection of compilers and computer architecture. The objective is to build a software toolchain (compiler, assembler, simulator, documentation, etc) that will allow programs written in <b>C-minor</b> to be compiled to the <b>albaCore </b>computer architecture. This package will be used in future offerings of logic design to assist students in running real, complex programs on custom FPGA hardware.<br />
<br />
Juniors or seniors who have taken either compilers or architecture (or both) are invited to apply by contacting either Prof. Thain (dthain@nd.edu) or Brockman (jbb@nd.edu). The project will be offered as a three-credit undergraduate research class in Spring 2018.<br />
<br />Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com0tag:blogger.com,1999:blog-4890039722003127341.post-30430407720834060912017-06-27T11:28:00.001-04:002017-06-27T11:28:09.662-04:00Talk at ScienceCloud WorkshopProf. Thain gave the opening talk, "<a href="http://www.nd.edu/~dthain/talks/sciencecloud-laptop-2017.pdf">Seamless Scientific Computing from Laptops to Cloud</a>s", at the <a href="https://sites.google.com/site/sciencecloudhpdc/">ScienceCloud</a> workshop preceding High Performance Distributed Computing 2017 in Washington, DC. This talk gives an overview of the problem of migrating scientific codes from the comfortable environment of a laptop to the complex environment of a cluster or a cloud, highlighting our new tools for software deployment and resource management for bioinformatics and high energy physics applications.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://www.nd.edu/~dthain/talks/sciencecloud-laptop-2017.pdf"><img border="0" data-original-height="540" data-original-width="720" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiyJ7US_1P1IksUaj5nZ7-zs4Kat3-pLiwnTkzJh9o89_fslFuOLn-82zt4CrvvxWPX8BPiwoWRbVCJOjSSKBmzg8i2r27JmvSVnEYNtBGx1IlpcW8MWi2DMRHOOr604007p2JEZjN0XtbH/s320/sciencecloud-laptop-2017.png" width="320" /></a></div>
<br />Douglas Thainhttp://www.blogger.com/profile/12930374395317667662noreply@blogger.com0tag:blogger.com,1999:blog-4890039722003127341.post-42525150406049937262017-05-31T09:39:00.000-04:002017-05-31T09:39:14.352-04:00Online Course in Data Intensive Scientific ComputingWe are happy to announce the pilot of a new <a href="https://edge.edx.org/courses/course-v1:NotreDame+00000+00/info?">online short course</a> in Data Intensive Scientific Computing. This is the equivalent of a one-credit seminar which provides an introduction to the challenges of scientific computing at large scale and the tools used to address those problems.<br />
<br />
The course was designed to augment our <a href="http://disc.crc.nd.edu/">summer REU program in DISC</a>, but is also suitable for undergraduate students taking research credits, and for graduating students in all disciplines looking for an introduction to topics and tools in scientific computing.<br />
<br />
By default, the online course is ungraded: anyone is welcome to sign up, view the lectures, take the quizzes, and follow the tutorials. If you want to receive a grade, talk to a faculty member at your institution to see if they will work with you on the material.<br />
<br />
The course is developed by <a href="http://www.nd.edu/~dthain">Prof. Douglas Thain</a> and <a href="http://www.nd.edu/~pbrenne1">Prof. Paul Brenner</a>, produced by the <a href="http://online.nd.edu/">Office of Digital Learning</a> at the <a href="http://www.nd.edu/">University of Notre Dame</a>, and offered through the <a href="http://edge.edx.org/">EdX Edge</a> platform.<br />
<br />
You can check out a sample lecture here:<br />
<br />
<br />
<iframe allowfullscreen="" frameborder="0" height="300" src="https://www.youtube.com/embed/vPJnsB6d0Ws" width="480"></iframe>
<br />
And here is an overview of the course structure:<br />
<br />
<img src="https://www3.nd.edu/~dthain/courses/disc/outline.png" style="max-width: 100%; min-width: 256px;" />Douglas Thainhttp://www.blogger.com/profile/12930374395317667662noreply@blogger.com160tag:blogger.com,1999:blog-4890039722003127341.post-30588329468412457392017-02-02T15:41:00.002-05:002017-02-02T15:41:35.236-05:00Writing a Compilers TextbookTo my surprise, I am in the final steps of writing a textbook! You can see a sample chapter today at <a href="http://compilerbook.org/">compilerbook.org</a>.<br />
<br />
The effort began in the fall of 2016, as I was putting together my materials for CSE 40243, our undergraduate class in Compilers and Language Design. This class focuses on the challenges of engineering a working language: students implement a working compiler that translates a C-like language into X86 assembly.<br />
<br />
While there are a variety of solid textbooks that are great for a graduate course in compiler theory and optimization, none quite had the flavor I was looking for. Nearly every CS grad needs to write a parser, evaluator, or translator for some kind of little language in their career, but relatively few need to dig deeply into assembly language optimization. So, I wanted to focus on language design choices and show that simple languages are not hard to implement.<br />
<br />
I began to combine my handwritten chalkboard notes and some sample code into a LaTeX document, and the next thing you know, I have seven chapters written. I expect to finalize everything in the spring 2017 semester.<br />
<br />
What has made it relatively easy so far is that my compiler automatically generates many of the figures and code examples automatically, so relatively few things have to be drawn by hand. For example, this sample AST is produced automatically by the compiler emitting Graphviz DOT code from the internal representation. Neat, eh?<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg6AUx1SdJg7VEHGsjh2hfgyFk95R37q3AisGLrhNLyxgg6JQafIH02s0fZKyX_-KtN9i8ztkiHIx0vhyphenhyphen8M5LWpb2EfpuigEPc6j2Xr5MeEDYVX3qa9phHOisxMGUaRaFkx2pRc4B9Du7k/s1600/ast.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="385" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg6AUx1SdJg7VEHGsjh2hfgyFk95R37q3AisGLrhNLyxgg6JQafIH02s0fZKyX_-KtN9i8ztkiHIx0vhyphenhyphen8M5LWpb2EfpuigEPc6j2Xr5MeEDYVX3qa9phHOisxMGUaRaFkx2pRc4B9Du7k/s400/ast.png" width="400" /></a></div>
<br />
<br />
Following the example of Remzi and Andrea Arpaci-Dusseau with <a href="http://ostep.org/" target="_blank">OSTEP</a> the book will be made available for free online in PDF form, and also in an inexpensive hardcover edition printed on-demand.<br />
<br />
Stay tuned for the release later in 2017...<br />
<div>
<br /></div>
Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com3tag:blogger.com,1999:blog-4890039722003127341.post-37746556322966863572016-04-05T10:02:00.001-04:002016-04-05T10:02:12.176-04:00NunyaOS: An Experimental OS KernelThis semester, I am organizing an experimental class around the design of an operating system kernel. Six students formed a team in response to a call for volunteers, and now busy designing <a href="http://nunyaos.github.io/" target="_blank">NunyaOS</a>, an experimental OS kernel. Building on top of the <a href="https://github.com/dthain/basekernel" target="_blank">Basekernel</a>, they have built a system that boots an X86 machine, reads a CD-ROM filesystem, runs multiple processes in paged virtual memory, and has a simple windowing system. We are off too a good start.<div>
<br /></div>
<div>
To try it out, download the source, build it, and run it in a VM like this:</div>
<div>
<span style="font-family: Courier New, Courier, monospace;">qemu-system-i386 --cdrom basekernel.iso</span></div>
<div>
<br /><div>
The key organizing principle of NunyaOS is <b>hierarchical containment</b>. This means that each process lives within a security container. Within that container, the process has complete authority to manipulate its resources. It also has the power to create sub-containers and then place child processes within them. The containment can be applied to each of the resources within the system -- currently the filesystem, the window system, and the memory allocator. As a result, each process lives a in a sort of a lightweight virtual machine, where it perceives itself to be the superuser.</div>
<div>
<br /></div>
<div>
For example, here are a few nested containers, each with their own filesystem root, display, and memory allocation:</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhqzGG1rjIc-dZp3oukGI0nhEPFNXfnAgaJO3RUYKatjo4cfDWqoTmWmtYVTaPaOIey1GmTgiJpYtcin46hWR8KYOgRMH-71Nogf_Zz_5aAU6PbhmLWoBzonb52xVZAtce_VGO_ALXXQTI/s1600/Containers.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhqzGG1rjIc-dZp3oukGI0nhEPFNXfnAgaJO3RUYKatjo4cfDWqoTmWmtYVTaPaOIey1GmTgiJpYtcin46hWR8KYOgRMH-71Nogf_Zz_5aAU6PbhmLWoBzonb52xVZAtce_VGO_ALXXQTI/s320/Containers.png" width="320" /></a></div>
<div>
<br /></div>
<div>
Ideally, every child process will live in a container, so that we can eliminate attack vectors between code provided from different sources. For example, your desktop should run your web browser in a container, your web browser should run each tab in a container, and each tab should run downloaded code (like a video codec) in yet another container. In this way, untrusted code has very little leeway to affect other elements of your system.</div>
<div>
<br /></div>
<div>
Of course, this idea changes the customs by which processes interact with each other. We can no longer build programs that scatter data all over the filesystem, and expect others to read it. There are many challenges here, and we have only begun to dig into them.</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
</div>
Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com2tag:blogger.com,1999:blog-4890039722003127341.post-26785203595408252332015-09-16T12:27:00.001-04:002015-09-16T12:28:44.004-04:00Sandboxes, Distributed Computing, and ClosuresThe <b>sandbox abstraction</b> comes up over and over again in the context of distributed computing. We didn't invent it, but it appears so frequently that it's worth giving it a name and explaining how it works. This abstraction is our model of execution in the <a href="http://ccl.cse.nd.edu/software/makeflow" target="_blank">Makeflow</a> workflow system, the <a href="http://ccl.cse.nd.edu/software/workqueue" target="_blank">Work Queue</a> master-worker framework, the <a href="http://ccl.cse.nd.edu/software/umbrella" target="_blank">Umbrella</a> environment generator, and other systems, and this is what enables these tools to interoperate.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJNW4Uw454pWRB6Esk3M3jLi1xzJRS3ShNWajiGQDGPEkqNIPd6je8NOhW97hnv8I6S11fQEH43NdddMCOOQgZOIjGU5E9ZXroOruWLuNxmG7lU1X2q1wVklBevzZ9T0Id1d6fsZ4tdb0/s1600/Sandbox.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJNW4Uw454pWRB6Esk3M3jLi1xzJRS3ShNWajiGQDGPEkqNIPd6je8NOhW97hnv8I6S11fQEH43NdddMCOOQgZOIjGU5E9ZXroOruWLuNxmG7lU1X2q1wVklBevzZ9T0Id1d6fsZ4tdb0/s320/Sandbox.png" width="320" /></a></div>
<br />
The sandbox abstraction is a way of specifying a remote execution in a way that can be efficiently delivered and precisely reproduced. To run a task, the user states the following:<br />
<br />
<div style="text-align: center;">
<b>run C = T( A, B ) in environment E</b></div>
<div>
<br /></div>
<div>
In this example, A and B are the input files to the task, T is the command to be run, and C is the output file produced. (Obviously, there can be more input and output files as needed.)</div>
<div>
<br /></div>
<div>
The sandbox itself is a <b>private namespace</b> in which the task can run, isolated from the outside world. This enables the task to perceive the input and output files in a different way than the called. A sandbox can be implemented in many ways: the simplest is just a plain old directory, but it could a Linux container or even a whole virtual machine.</div>
<div>
<br /></div>
<div>
The environment E is all the additional data that needs to be present within the sandbox: the operating system, the filesystem tree, program binaries, scripts, etc, which are represented by L1, L2, and L3 above. The environment must be compatible with the sandbox technology. For example, a tarball is a sufficient environment for executing within a directory sandbox, while a virtual machine image is needed for a virtual machine sandbox. </div>
<div>
<br /></div>
<div>
Now, the pieces must all come together: The sandbox must be created and the environment unpacked within it. The input files must be moved to the execution site and copied or otherwise connected to the sandbox. The task is run, producing the output, which must then be moved outside of the sandbox to the desired location. Then, the sandbox may be discarded.</div>
<div>
<br /></div>
<div>
Once you begin to execute all tasks using the sandbox abstraction, many things become easier.</div>
<div>
<ul>
<li>Executing tasks at remote sites becomes very easy, because all of the necessary dependencies are explicit and can be moved around the world. (e.g. <a href="http://ccl.cse.nd.edu/software/workqueue" target="_blank">Work Queue</a>) </li>
<li>Similar tasks running on the same machine can share input objects, to improve efficiency. (e.g. <a href="http://ccl.cse.nd.edu/software/umbrella" target="_blank">Umbrella</a>)</li>
<li>Multiple tasks can be chained together while respecting independent namespaces. (e.g. <a href="http://ccl.cse.nd.edu/software/makeflow" target="_blank">Makeflow</a>)</li>
</ul>
</div>
<div>
Of course, all of these properties are not accidental: they have a good precedent in the realm of language theory. A sandbox execution is really just a <a href="https://en.wikipedia.org/wiki/Closure_(computer_programming)" target="_blank">closure</a>, which is the name for a function combined with an environment, which is a set of bindings from names to values.</div>
Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com1tag:blogger.com,1999:blog-4890039722003127341.post-89013769580588673932015-05-20T23:39:00.001-04:002015-05-20T23:39:32.686-04:00Writing Solid Tests is (Still) HardWe have a nice little <a href="http://ccl.cse.nd.edu/software/autobuild" target="_blank">automatic build-and-test system</a> for the Cooperative Computing Tools which has nicely brought together the capabilities of Github, Condor, and Docker.<br /><span style="text-align: center;"><br /></span>
<span style="text-align: center;">Every proposed merge to the codebase is packaged up as a build job which is dispatched to our Condor pool. Some of those jobs run natively on bare hardware, some jobs run on virtual machines, and some are running in Docker containers, but all of them are managed by Condor, so we can have a zillion builds going simultaneously without too much conflict.</span><br />
<br />
The result is that anytime someone proposes a pull request, it gets run through the system and a few minutes later we get a new row on the web display that shows whether each platform built and tested correctly. It's very handy, and provides for objective evaluation and gentle pressure on those who break the build.<br />
<br />
<i>(I should point out here that Patrick Donnelly and Ben Tovar have done a bang-up job of building the system, and undergraduate student Victor Hawley added the Docker component.)</i><br />
<div>
<i><br /></i></div>
Some days the board is all green, and some days it looks more like this:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://ccl.cse.nd.edu/software/autobuild" target="_blank"><img border="0" height="125" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj8SXOufHKSHpicmZj3OzD8rxGJ2Jtlbc0eC7QSG19z67bms8Jc7QAr1XD8cDvEncNvnC5_y6NJ4NSYucfVTmKnBXWjPP7zeO1-Or9jcuy-pHD4a5NpncdaXLL4gBoJcLfqEDr9ojr89aY/s200/Screen+Shot+2015-05-20+at+11.04.38+PM.png" width="200" /></a></div>
<div>
<br /></div>
<br />
But the hardest part of this seems to be writing the tests properly. Each test is a little structured script that sets up an environment, runs some component of our software, and then evaluates the results. It might start up a Chirp server and run some file transfers, or run Parrot on a tricky bit of Unix code, or run Makeflow on a little workflow to see if various options work correctly.<br />
<br />
Unfortunately, there are many ways that the tests can fail without revealing a bug in the code! We recently added several platforms to the build, resulting in a large number of test failures. Some of these were due to differences between Unix utilities like <b>sh</b>, <b>dd</b>, and <b>sed</b> on the various machines. Others were more subtle, resulting from race conditions in concurrent actions. (For example, should you start a Master in the foreground and then a Worker in the background, or vice versa.) There is a certain art to being able to write a shell script that is portable and robust.<br />
<br />
There is also a tension in the complexity of the tests. On one hand, you want short, focused tests that exercise individual features, so that they can be completed in a few minutes at give immediate feedback.<br />
<br />
On the other hand, you also want to run big complex applications, so as to test the system at scale and under load. We don't really know that a given release of Parrot works at scale until it has run on 10K cores for a week for a CMS physics workload. If each core consumes 30W of power over 7 days, that's a <b>50 megawatt-hour</b> test! Yikes!<br />
<br />
Better not run that one automatically.<br />
<br />
<br />Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com0tag:blogger.com,1999:blog-4890039722003127341.post-14257634377384493082014-05-19T15:14:00.000-04:002014-05-19T15:14:02.421-04:00Toward a Common Model of Highly Concurrent Programming(This is the short version of a talk I gave at the MTAGS workshop at Supercomputing 2013. <a href="http://www3.nd.edu/~dthain/talks/model-mtags13.pptx" target="_blank">See the slides here</a>.)<br />
<br />
Historically, highly concurrent programming has been closely associated with high performance computing. Two programming models have been dominant: shared memory machines in which concurrency was expressed via multiple threads, and distributed memory machines in which concurrency was expressed via explicit message passing. It is widely agreed that both of these programming models are very challenging, even for the veteran programmer. In both cases, the programmer is directly responsible for designing the program from top to bottom and handling all of the issues of granularity, consistency, and locality necessary to achieve acceptable performance, with very little help from the runtime or operating systems.<br />
<br />
However, a new approach to concurrent programming has been emerging over the last several years, in which the user programs in a much higher level language and relies upon the system to handle many of the challenging underlying details. To achieve this, the program is successively decomposed into simpler representations, such that each layer of the system can gradually adapt it to the hardware available.<br />
<br />
The layers can be described as follows:<br />
<ul>
<li>A <strong>declarative language (DL)</strong> for compactly representing a complete program.</li>
<li>A <strong>directed graph (DAG)</strong> to represent the expanded program and its resources.</li>
<li>A <strong>bag of independent tasks (BOT)</strong> with explicit input and output dependencies.</li>
<li>A <b>shared-nothing cluster </b>to which data and tasks must be assigned.</li>
</ul>
Several different research communities have arrived at this computing model somewhat independently: the high performance computing community, the scientific workflow community, and the cloud computing community. In each case, the scale and complexity of the systems in use eventually made it impossible for the programmer or the user to take responsibility for all of the challenges of parallel/distributed computing. Although each community employs different technologies and has distinct optimization goals, the overall structure of these systems is surprisingly similar.
<br />
<br />
A (very incomplete) selection of systems that follow this model:<br />
<br />
<div>
<br />
<table>
<tbody>
<tr>
<td><b>Layer
</b></td><td><b>Cloud Stack
</b></td><td><b>Workflow Stack
</b></td><td><b>HPC Stack</b>
</td></tr>
<tr>
<td>Declarative Language (DL) </td><td>Pig
</td><td>Weaver
</td><td>Swift-T
</td></tr>
<tr>
<td>Directed Acyclic Graph (DAG)</td><td>Map-Reduce </td><td>Makeflow
</td><td>-
</td></tr>
<tr>
<td>Bag of Tasks (BOT)</td><td>JobTracker
</td><td>Work Queue Master
</td><td>Turbine
</td></tr>
<tr>
<td>Distributed Data
</td><td>HDFS
</td><td>Work Queue Workers </td><td>MPI
</td></tr>
</tbody></table>
<br />
Each layer of the system fulfills a distinct need. The declarative language (DL) at the top is compact, expressive, and easy for end users, but is intractable to analyze in the general case because it may have a high order of complexity, possibly Turing-complete. The DL can be used to generate a (large) directed acyclic graph (DAG) that represents every single task to be executed. The DAG is not a great user-interface language, but it is much more suitable for a system to perform capacity management and optimization because it is a finite structure with discrete components. A DAG executor then plays the graph, dispatching individual tasks as their dependencies are satisfied. The BOT consists of all the tasks that are ready to run, and is then scheduled onto the underlying computer, using the data dependencies made available from the higher levels.<br />
<br />
Why bother with this sort of model? It allows us to compare the fundamental capabilities and expressiveness of different kinds of systems. For example, in the realm of compilers, everyone knows that a proper compiler consists of a scanner, a parser, an optimizer, and a code generator. Through these stages, the input program is transformed from a series of tokens to an abstract syntax tree, an intermediate representation, and eventually to assembly code. Not every compiler uses all of these stages, much less the same code, but by using a common language, it is helpful to understand, compare, and design new systems.<br />
<br />
<br /></div>
Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com0tag:blogger.com,1999:blog-4890039722003127341.post-43143947760042242482014-02-14T11:20:00.002-05:002014-02-17T15:48:21.749-05:00Visualizing 10,000 CoresOur Condor pool at the University of Notre Dame has been slowly growing, in no small part due to our collaboration with the Center for Research Computing, where it is now scavenging unused cycles from HPC clusters at the CRC. When the dedicated batch system leaves a node unused, Condor is started on that node and keeps going until the dedicated system wants the node back. Depending on the time of year, that leaves anywhere between 4K and 10K nodes available in the Condor pool.<br />
<br />
We have tried a number of approaches at visualizing this complex system over the years. Our latest tool, the <a href="http://condor.cse.nd.edu/condor_matrix.cgi" target="_blank">Condor Matrix Display</a> started as a summer project by Nick Jaeger, a student from the University of Wisconsin at Eau Claire. The display shows a colored bar for each slot in the pool, where the width is proportional to the number of cores. <br />
<br />
With a quick glance, you can see how many users are busy and whether they are running "thin" (1 core) or "fat" (many core) jobs. Sorting by the machine name gives you sense of how each sub-cluster in the pool is used:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjuUBYlsM6Cflm3iMo97gJFRSAF-X80379d1vhJMN7NHDanYtu6tpeU-zySENdvVvF7LWqJX0C2WxcImcZCKUQB5LGKxXgK05oFupiGwTARyG5sbIh5tbL7r2xs7GPTZ_jXgzexImVFEb0/s1600/condormatrix.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjuUBYlsM6Cflm3iMo97gJFRSAF-X80379d1vhJMN7NHDanYtu6tpeU-zySENdvVvF7LWqJX0C2WxcImcZCKUQB5LGKxXgK05oFupiGwTARyG5sbIh5tbL7r2xs7GPTZ_jXgzexImVFEb0/s1600/condormatrix.gif" height="200" width="320" /></a></div>
<br />
While sorting by users gives you a sense of what users are dominating the pool:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgfCVnxoOWBdy5P7KKr9Vctwn9mxRFDVYL5PviaeoRfaTUtyjYJe9r_9euyxFk1-T2XOFeGh0c2JQLYFDHewB40YWO0GbpLUBX03dWnqB-Pn6sF8XfXo8iJ1SF7LmXYnuDsB0t2eFqTVxo/s1600/condormatrixusers.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgfCVnxoOWBdy5P7KKr9Vctwn9mxRFDVYL5PviaeoRfaTUtyjYJe9r_9euyxFk1-T2XOFeGh0c2JQLYFDHewB40YWO0GbpLUBX03dWnqB-Pn6sF8XfXo8iJ1SF7LmXYnuDsB0t2eFqTVxo/s1600/condormatrixusers.gif" height="200" width="320" /></a></div>
<br />
The display is always a nice way of viewing the relatively new feature of "dynamic slot" in Condor. A large multi-core machine is now represented as a single slot with multiple resources. For example, this bit of the display shows a cluster of 8-core machines where some of the machines are unclaimed (green), some are running 4-core jobs (blue), and some are running 1-core jobs (green):<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjIlu-VU1ySbIXapkCz1ZENdP1zJ5quwcyPEvvm4DKcLqevcXDV2OO8t-kpHcr5PaeLSlDf7LPdVeUEzSao5sY2Ay-B_is229kXYJeDzeD2FAKTp7e_i62LIv9wP32e0xa5Rk8cIyBtT6s/s1600/condorselection.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjIlu-VU1ySbIXapkCz1ZENdP1zJ5quwcyPEvvm4DKcLqevcXDV2OO8t-kpHcr5PaeLSlDf7LPdVeUEzSao5sY2Ay-B_is229kXYJeDzeD2FAKTp7e_i62LIv9wP32e0xa5Rk8cIyBtT6s/s1600/condorselection.gif" height="39" width="320" /></a></div>
<br />
<span id="goog_991946909"></span><br />Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com0tag:blogger.com,1999:blog-4890039722003127341.post-6515888704183737382012-02-06T08:00:00.000-05:002012-02-06T08:00:07.275-05:00Some Open Computer Science Problems in Workflow SystemsIn the previous <a href="http://dthain.blogspot.com/2012/02/why-makeflow-works-for-new-users.html">article</a>, I extolled the virtues of <a href="http://www.cse.nd.edu/%7Eccl/software/makeflow">Makeflow</a>, which has been very effective at engaging new users and allowing them to express their workflows in a way that facilitates parallel and distributed computing. We can very consistently get new users going from one laptop to 100 cores in a distributed system very easily.<br />
<br />
However, as we develop experience in scaling up workflows to thousands of cores across wide area distributed systems, a number of interesting computer science challenges have emerged. These problems are not specific to Makeflow, but can be found in most workflow systems:<br />
<br />
<b>Capacity Management<br /></b>Just because a workflow expresses thousand-way concurrency doesn't mean that it is actually a good idea to run it on one thousand nodes! The cost of moving data to and from the execution nodes may outweigh the benefit of the added computational power. If one uses fewer nodes than the available parallelism, then it may be possible to pay the data movement cost once, and then exploit it multiple times. For most workflows, there is a "sweet spot" at which performance is significantly maximized. Of course, users don't want to discover this by experiment, they need some tool to recommend an appropriate size for the given workflow.<br />
<br />
<div>
</div>
<div>
<b>Software Engineering Tools<br /></b>A workflow is just another kind of program: it has source code that must be managed, dependencies that must be gathered, and a history of modification to be tracked. In this sense, we are badly in need of tools for manipulating workflows in coherent ways. For example, we need a <i>linker</i> that can take a workflow, find all the dependent components, and gather them together in one package. We need a <i>loader</i> that can take an existing workflow, load it into a computing system, and then update file names and other links to accomodate it. We need a <i>profiler</i> that can report on the time spent across multiple runs of a workflow, so as to determine where problem spots may be.</div>
<div>
</div>
<div>
<b><br /></b><span style="font-weight: bold;">Portability and Reproducibility<br /></span>Makeflow itself enables portability across execution systems. For example, you can run your application on Condor or SGE without modification. However, that doesn't mean that your applications are actually portable. If one cluster runs Blue Beanie Linux 36.5 and another runs Green Sock Linux 82.7, your chances of the same executable running on both are close to zero. Likewise, if you run a workflow one day, then set it aside for a year, it's possible that your existing machine has been updated to the point where the old workflow no longer runs.<br />
<br />
However, if we also explicitly state the <span style="font-style: italic;">execution environment</span> in the workflow, then this can be used to provide applications with what they need to run. The environment might be as simple as a directory structure with the applications, or as complex as an entire virtual machine. Either way, the environment becomes data that must be managed and moved along with the workflow, which affects the performance and cost issues discussed above.<br />
<br />
<b>Composability<br /></b>Everything in computing must be composable. That is, once you get one component working, the very next step is to hook it up to another so that it runs as a subcomponent. While we can technically hook up one Makeflow to another, this doesn't currently happen in a way that results in a coherent program. For example, the execution method and resource limits don't propagate from one makeflow to another. To truly enable large scale structures, we need a native method of connecting workflows together that connects not only the control flow, but the resource allocation, capacity management, and everything else discussed above.<br />
<br />
<span style="font-weight: bold;">Effortless Scalability</span><br />
<br />
As a rule of thumb, I tell brand new users that running a Makeflow on 10 cores simultaneously is trivial, running on 100 cores is usually easy, and getting to 1000 cores will require some planning and debugging. Going over 1000 cores is possible (our largest system is running on 5000 cores) but requires a real investment of time by the user.<br />
<br />
Why does scale make things harder? One reason is that computer systems are full of artificial limits that are not widely know or managed effectively. On a Unix-like system, a given process has a limited number of file descriptors per process and a limited number of files per directory. (Most people don't figure this out until they hit the limit, and then the work must be restructured to accomodate.) A complex network with translation devices may have a limited number of simultaneously network connections. A data structure that was small to ignore suddenly becomes unmanageable when there are 10,000 entries.<br />
<br />
To have a software system that can scale to enormous size, you need to address these known technical issues, but also have methods of accomodating limits that you didn't expect. You also need an architecture that can scale naturally and observe its own limits to understand when they are reached. An ideal implementation would know its own limits and not require additional experts in order to scale up.<br />
<br />
---<br />
<br />
Each of these problems, though briefly described, are pretty hefty problems once you start digging into them. Some of them are large enough to earn a PhD. (In fact, some are already in progress!) They all have the common theme of making data intensive workflows manageable, useable, portable, and productive across a wide variety of computing systems.<br />
<br />
More to follow.<br />
<br /></div>Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com2tag:blogger.com,1999:blog-4890039722003127341.post-36305203615330022852012-02-01T16:27:00.008-05:002012-02-02T12:37:37.899-05:00Why Makeflow Works for New Users<div>In past <a href="http://dthain.blogspot.com/2009/07/make-as-abstraction-for-distributed.html">articles</a>, I have introduced <a href="http://www.nd.edu/%7Eccl/software/makeflow">Makeflow</a>, which is a large scale workflow engine that we have created at Notre Dame.<br /><br />Of course, Makeflow is certainly not the first or only workflow engine out there. But, Makeflow does have several unique properties that make it an interesting platform for bringing new people into the world of distributed computing. And, it is the right level of abstraction that allows us to address some fundamental computer science problems that result.<br /><br />Briefly, Makeflow is a tool that lets the user express a large number of tasks by writing them down as a conventional makefile. You can see an example on our web page. A Makeflow can be just a few rules long, or it can consist of hundreds to thousands of tasks, like this EST pipeline workflow:<br /><br /></div><div><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXC_1vAAJx2XPYyO0OAhklCcX_iu9COeQdrykmw7Ldmhlh_RpROrFivK7z1_2Pj5cn0CCoXIS8t8jdx6945oGKY0mbfzclkuv9s5XVlUnqE1u2fy1k569jXEKbzt7IkV92I4D2Hp3-Uu4/s1600/makeflow.png"><img style="display: block; margin: 0px auto 10px; text-align: center; cursor: pointer; width: 400px; height: 194px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXC_1vAAJx2XPYyO0OAhklCcX_iu9COeQdrykmw7Ldmhlh_RpROrFivK7z1_2Pj5cn0CCoXIS8t8jdx6945oGKY0mbfzclkuv9s5XVlUnqE1u2fy1k569jXEKbzt7IkV92I4D2Hp3-Uu4/s400/makeflow.png" alt="" id="BLOGGER_PHOTO_ID_5704585659517100274" border="0" /></a>Once the workflow is written down, you can then run Makeflow in several different ways. You can run it entirely on your workstation, using multiple cores. You can ask Makeflow to send the jobs to your local <a href="http://www.cs.wisc.edu/condor">Condor</a> pool, PBS or SGE cluster, or other batch system. Or, you can start the (included) <a href="http://www.nd.edu/%7Eccl/software/workqueue">Work Queue</a> system on a few machines that you happen to have handy, and Makeflow will run the jobs there.<br /><br />Over the last few years, we have had very good experience getting new users to adopt Makeflow, ranging from highly sophisticated computational scientists all the way to college sophomores learning the first principles of distributed computing. There are a couple of reasons why this is so:</div><ul><li><span style="font-weight: bold;">A simple and familiar language.</span> Makefiles are already a well known and widely used way of expressing dependency and concurrency, so it is easy to explain. Unlike more elaborate languages, it is brief and easy to read and write by hand. A text-based language can be versioned and tracked by any existing source control method.</li><li><span style="font-weight: bold;">A neutral interface and a portable implementation. </span> Nothing in a Makeflow references any particular batch system or distributed computing technology, so existing workflows can be easily moved between computing systems. If you I use Condor and you use SGE, there is nothing to prevent my workflow from running on your system.</li><li><span style="font-weight: bold;">The data needs are explicit. </span> A subtle but significant difference between Make and Makeflow is that Makeflow treats your statement of file dependencies very seriously. That is, you must state exactly which files (or directories) that your computation depends upon. This is slightly inconvenient at first, but vastly improves the ability of Makeflow to create the right execution environment, verify a correct execution, and manage storage and network resources appropriately.</li><li><span style="font-weight: bold;">An easy on-ramp to large resources. </span> We have gone to great lengths to make it absolutely trivial to run Makeflow on a single machine with no distributed infrastructure. Using the same framework, you can move to harnessing a few machines in your lab (with Work Queue) and then progressively scale up to enormous scale using clusters, clouds, and grids. We have users running on 5 cores, 5000 cores, and everything in between.</li></ul><div>Of course, our objective is not simply to build software. Makeflow is a starting point for engaging our research collaborators, which allows us to explore some hard computer science problems related to workflows. In the next article, I will discuss some of those challenges.<br /><br /><br /></div>Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com0tag:blogger.com,1999:blog-4890039722003127341.post-51597515023238737542010-11-16T13:00:00.003-05:002010-11-16T14:02:38.174-05:00The Virtualization Theorem Ignored for Three DecadesToday, in my graduate operating systems class, we discussed what I believe is the most important result in computer science ever to be <span style="font-weight: bold;">persistently ignored</span>:<br /><br />Popek and Goldberg,<a href="http://portal.acm.org/citation.cfm?id=361011.361073"> Formal Requirements for Virtualizible Third Generation Architectures</a>, Communications of the ACM, Volume 17, Issue 7, July 1974.<br /><br />This paper puts forth a very simple principle that must be observed in order for a CPU to be capable of running in a virtual machine. First, two definitions:<br /><ul><li>A <span style="font-style: italic; font-weight: bold;">sensitive</span> instruction reads or modifies supervisor state</li><li> A <span style="font-weight: bold; font-style: italic;">privileged</span> instruction traps if attempted in user mode.</li></ul> And this central theorem:<br /><ul><li><span style="font-weight: bold; font-style: italic;">All sensitive operations must be privileged.</span></li></ul>Here is why this is important. A conventional operating system (OS) is in charge of the whole machine, and is free to modify the processor status, page tables, I/O devices, and other sensitive aspects of the machine in order to run normal processes.<br /><br />But, if you take that OS and put it in a virtual machine (VM), it is no longer in charge of the whole machine. All of those actions on sensitive state must be <span style="font-weight: bold;">translated </span>in some way by the virtual machine monitor. The simplest way to accomplish that translation is to run the OS in user mode, allowing the VMM to execute sensitive operations on its behalf. To make sure that the VMM gets all of the sensitive operations, they must all be forced to trap.<br /><br />This principle was articulated very clearly in 1974, when virtualization was already a widely applied technique in the world of mainframe computing. Unfortunately, the principle didn't make the leap into the microcomputer world. In fact, there was an enduring tradition of releasing processors that were not virtualizable, only to realize the mistake and issue a second version with a minor fix.<br /><br />For example, the venerable <a href="http://en.wikipedia.org/wiki/Motorola_68000">Motorola 68000</a> was first released in 1978, and was heralded as a "mainframe on a chip". Except, it had one little problem: a read from the sensitive status register did not trap, preventing the construction of a virtual memory system. So, Motorola issued the <a href="http://en.wikipedia.org/wiki/Motorola_68010">68010</a>, which was <span style="font-weight: bold;">almost identical</span>, except that a read from the status register forced a trap, enabling correct virtualization of memory.<br /><br />Unfortunately, not everybody got the memo.<br /><br />For nearly three decades, the Intel x86 series of processors did not have this property. In user mode, many instructions could be used to view sensitive state, and many attempts to write sensitive state would fail silently without a trap. From the 1970s until the late 1990s, efficient virtualization was basically impossible on the most widely used processor family.<br /><br />Around the year 2000, virtualization became of interest as a way to service the multi-tenancy needs of large internet services. A number of solutions were developed simultaneously to work around the limitations of the Intel chips. One approach used in VMWare was to dynamically compile assembly code at runtime to convert sensitive instructions into deliberate traps to the VMM. Another approach used in the Xen hypervisor was to modify the operating system code so that it explicitly called the VMM instead of invoking sensitive instructions.<br /><br />There are many other approaches to working around the limitation. Suffice to say that they are all rather complicated, but they can be made to work.<br /><br />Finally, in 2005, both Intel and AMD introduced virtualization extensions to their processors, enabling basic trap-and-execute virtualization, only <span style="font-weight: bold;">29 years</span> after the Popek and Goldberg theorem was widely circulated.<br /><br />So, what's the moral of the story?Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com1tag:blogger.com,1999:blog-4890039722003127341.post-4115206100553539752010-11-08T11:00:00.004-05:002010-11-08T11:00:03.381-05:00Sometimes It All Comes TogetherMost days, software engineering involves compromises and imperfect solutions. It's rare for two pieces of software to mesh perfectly -- you always have to work to overcome the limitations or assumptions present in different modules. But, every once in a while, the pieces just come together in a satisfying way.<br /><br />A few weeks back, we ran into a problem with BXGrid, our system for managing biometric data. Our users had just ingested a whole pile of new images and videos, and were browsing and validating the data. Because data was recently ingested, no thumbnails had been generated yet, so every screenful required a hundred or so thumbnails to be created from the high resolution images. Multiple that by each active user, and you have a web site stuck in the mud.<br /><br />A better solution would be to generate all of the missing thumbnails offline in an orderly way. Since many of the transcoding operations are compute intensive, it makes sense to farm them out to a distributed system.<br /><br />Peter Bui -- a graduate student in our group -- solved this problem elegantly by putting together almost all of our research software simultaneously. He used <a href="http://dthain.blogspot.com/search/label/weaver">Weaver</a> as the front-end language to query <a href="http://dthain.blogspot.com/search/label/bxgrid">BXGrid</a> and determine what thumbnails needed to be generated. Weaver generated a <a href="http://dthain.blogspot.com/search/label/makeflow">Makeflow</a> to perform all of the transcodings. Makeflow used <a href="http://dthain.blogspot.com/search/label/work%20queue">Work Queue</a> to execute the tasks, with the Workers submitted to our campus <a href="http://dthain.blogspot.com/search/label/condor">Condor</a> pool.<br /><br />So far, so good. But, the missing piece was that Makeflow expects data to be available as ordinary files. At the time, this would have required that we copy several terabytes out of the archive onto the local disk, which wasn't practical. So, Peter wrote a module for Parrot which enabled access to BXGrid files under paths like<span style="font-family:courier new;"> /bxgrid/fileid/123</span>. Then, while attached to <a href="http://dthain.blogspot.com/search/label/parrot">Parrot</a>, Makeflow could access the files, being none the wiser that they were actually located in a distributed system.<br /><br />Put it all together, and you have this:<br /><br /><img style="TEXT-ALIGN: center; MARGIN: 0px auto 10px; WIDTH: 447px; DISPLAY: block; HEIGHT: 354px; CURSOR: hand" id="BLOGGER_PHOTO_ID_5532826642233001490" border="0" alt="" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjX2Ew27DNU6vqDv1KYon9qrvQXI5j8FXf6Zczod1sx7NSOoNDneHV0jP0OyYzAoX4L9iUnkCBIKljMiO2U5CEZat88eQS0VXPeSi9JT0zaOkNryyk580mL1SurM_E0ov4O8CmY_BgID1k/s400/everything.gif" /> Sometimes, it all comes together.Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com0tag:blogger.com,1999:blog-4890039722003127341.post-72959282712298780942010-11-01T11:00:00.005-04:002010-11-01T11:00:01.570-04:00Compiling Workflows with WeaverOver the last year, our <a href="http://www.cse.nd.edu/%7Eccl/software/makeflow">Makeflow</a> system has become quite popular here at Notre Dame. Briefly, Makeflow takes a workload expressed in the plain old Make format, and executes it in a distributed system, using the dependency information to set up the appropriate remote execution environment. It does not require a distributed filesystem, so it's easy to get your applications going on hundreds to thousands of processors from the cloud or the grid. Makeflow is currently the back-end engine for our science portals in bioinformatics, biometrics, and molecular dynamics.<br /><br />It didn't take long before our users started writing scripts in Perl or Python in order to generate Makeflows with tens of thousands of nodes. Those scripts all did similar things (query a database, break a dataset into N pieces) but also started to get unruly and difficult to debug. It wasn't easy to look at a script generator and determine what it was trying to accomplish.<br /><br />Enter Weaver, which is the creation of Peter Bui, one of our graduate students. Weaver is a high level Python framework that, in a few simple lines, can generate enormous (optimized) Makeflows. Peter presented a <a href="http://www.cse.nd.edu/%7Eccl/research/pubs/weaver-clade2010.pdf">paper about Weaver</a> at the workshop on Challenges of Large Applications in Distributed Environments at HPDC earlier this year.<br /><br />Consider this common biometrics workload: extract all of the blue irises from our repository, then convert each iris into a 'template' data type, then compare all of them to each other. Here is how you do it in Weaver:<br /><pre><br />b = SQLDataSet (’db’,’biometrics','irises')<br />nefs = Query(db,db.color='Blue')<br /><br />conv = SimpleFunction('convertiristotemplate',outsuffix='bit')<br />bits = Map(conv,nefs)<br /><br />cmp = SimpleFunction('compareiristemplates')<br />AllPairs(cmp,bits,bits,output='matrix.txt')<br /></pre><br />In the simplest case, Weaver just emits one gigantic Makeflow that performs all of the operations. However, sometimes there are patterns that can be executed more efficiently, given some better underlying tool. <a href="http://dthain.blogspot.com/search/label/allpairs">AllPairs</a> is the perfect example of this optimization -- you <span style="font-weight: bold;">can</span> do an AllPairs using Makeflow, but it won't be as efficient as our native implementation. If the various data types line up appropriately, Weaver will simply call the All-Pairs abstraction. If not, it will expand the call into Makeflow in the appropriate way.<br /><br />In principle, this is a lot like a C compiler: under certain conditions, the addition of two arrays can be accomplished with a vector add instruction, otherwise it must be expanded into a larger number of conventional instructions. So, we think of Weaver as a <span style="font-weight: bold;">compiler for workflows</span>: it chooses the best implementation available to execute a complex program, leaving the programmer to worry about the higher level objectives.Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com0tag:blogger.com,1999:blog-4890039722003127341.post-63924731681518199322010-10-27T11:00:00.002-04:002010-10-27T11:14:40.106-04:00From Database to Filesystem and Back AgainHoang Bui is leading the development of ROARS: a Rich Object Archival System, which is our generalization many of the ideas expressed in the <a href="http://dthain.blogspot.com/search/label/bxgrid">Biometrics Research Grid</a>. Hoang presented a <a href="http://cse.nd.edu/%7Eccl/research/pubs/roars-didc.pdf">paper on ROARS</a> at the workshop on Data Intensive Distributed Computing earlier this year.<br /><br />What makes ROARS particularly interesting is that it combines elements of both relational databases and file systems, and makes it possible to swap back and forth between both representations of the data.<br /><br />A ROARS repository is an unordered collection of items. Each item consists of a binary file and metadata that describes the file. The metadata does not have a schema; you can attach whatever properties you like to an object. Here is an example item consisting of a iris image with five properties:<br /><br /><a style="font-family: courier new;" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjte5Vgw8Op65vPCHDvrrB2zYxlRGebnrSRTkD5Zm8r_iwRo3V-kvAdssYwmcP6uHwRby0xQdKdETG8wdgxdlGElYkg-vSau0Jq00-aOt7Z0HbGhEExoL4YhWbR_SbGIISLdT84s360hQ0/s1600/iris.jpeg"><img style="margin: 0pt 10px 10px 0pt; float: left; cursor: pointer; width: 171px; height: 128px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjte5Vgw8Op65vPCHDvrrB2zYxlRGebnrSRTkD5Zm8r_iwRo3V-kvAdssYwmcP6uHwRby0xQdKdETG8wdgxdlGElYkg-vSau0Jq00-aOt7Z0HbGhEExoL4YhWbR_SbGIISLdT84s360hQ0/s320/iris.jpeg" alt="" id="BLOGGER_PHOTO_ID_5532734026263003362" border="0" /></a><span style="font-family:courier new;">fileid = 356</span><br /><span style="font-family:courier new;">subjectid = "S123"</span><br /><span style="font-family:courier new;">color = "Blue"</span><br /><span style="font-family:courier new;">camera = "Likon"</span><br /><span style="font-family:courier new;">date = "23-Oct-2010"</span><br /><span style="font-family:courier new;">type = "jpeg"</span><br /><br /><br /><br />If you like to think in SQL, then you can query the system via SQL and you get back tabular data, as you might expect:<br /><br /><span style="font-family:courier new;">SELECT fileid, subjectid, color FROM irises WHERE color='Blue';</span><br /><br />Of course, if you are going to actually process the files in some way, you need to put them into a filesystem where your scripts and tools can access them. For this, you use the EXPORT command, which will produce the files. EXPORT has a neat bit of syntax in which you can specify that the name of each file is generated from the metadata. For example this command:<br /><br /><span style="font-family:courier new;">EXPORT irises WHERE camera='Likon' AS color/subjectid.type</span><br /><br />will dump out all of the matching files, put them into directories according to color, and name each file according to the subject and the file type. The example above would be named "Blue/S123.jpeg". (If the naming scheme doesn't result in unique filenames, then you need to adjust it to include something that is unique like fileid.)<br /><br />Of course, if you are going to process a huge amount of data, then you don't actually want to copy all of it out to your local filesystem. Instead what you can do is create a "filesystem view" which is a directory tree containing pointers back to the objects in the repository. That has a very similar syntax:<br /><br /><span style="font-family:courier new;">VIEW irises WHERE camera='Likon' AS color/subjectid.type</span><br /><br />Creating a filesystem view is much faster than exporting the actual data. Now, you can run your programs or scripts to iterate over the files. As they open up each file, the repository is accessed directly to open and read the necessary file data. (This is accomplished transparently by using <a href="http://www.cse.nd.edu/%7Eccl/software/parrot/">Parrot</a> to connect to the repository.)<br /><br />The end result: a database that looks like a filesystem!Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com0tag:blogger.com,1999:blog-4890039722003127341.post-76014535970219988552010-10-18T12:04:00.017-04:002010-10-19T15:12:36.338-04:00Summer REU: Toward Elastic Scientific ApplicationsIn recent months, we have been working on the problem of building <span style="FONT-WEIGHT: bold">elastic parallel applications</span> that can adapt to the available resources at run-time. Much has been written about elastic internet services, but scientific applications have a ways to catch up.<br /><br />Traditional parallel applications are <span style="FONT-WEIGHT: bold">rigid</span>: the user chooses how many nodes (or cores or CPUs) to use when the program starts. If more resources become available, or the application needs to grow, it is stuck. Even worse, if a node is lost due to a failure or a scheduling change, the program must be aborted. Rigid parallelism has been used for many years in dedicated clusters and supercomputers in the form of libraries such as MPI. It works fine for systems of tens or hundreds of nodes, but if you try to go bigger, it gets harder and harder to find a fully reliable system.<br /><br />In contrast, an <span style="FONT-WEIGHT: bold">elastic</span> parallel application can be modified at run-time to use greater or fewer resources as they become available, or if the size of the problem changes. Typically, an elastic application has one central coordinating node that tracks the progress of the program, and dispatches work units to other nodes. If new nodes are added to the system, the coordinator gives it some work to do. If a node fails or is removed, the coordinator makes a note of this, and sends the work to another node.<br /><br />If you have an elastic application, then it becomes much easier to harness large scale computing systems such as clouds and grids. In fact, it becomes easier to harness any kind of computer, because you don't have to worry about them being reliable or even particularly fast. It's also useful in a traditional computing center, because you don't have to sit idle waiting for your ideal number of nodes to become free -- you can start work with whatever is available now.<br /><div><br /><div>The only problem is, most existing applications are rigidly parallel. Is it feasible to convert them into elastic applications?<br /><br />We hosted two REU students to address this question: Anthony Canino, from SUNY-Binghamtom, and Zachary Musgrave, from Clemson University. Each took an existing rigid application and converted it into an elastic parallel application using our <a href="http://www.cse.nd.edu/~ccl/software/workqueue">Work Queue</a> framework. Work Queue has a simple C API, and makes use of a universal Worker executable that can be submitted to multiple remote systems. A Work Queue application looks like this:<br /></div><img style="TEXT-ALIGN: center; MARGIN: 0px auto 10px; WIDTH: 315px; DISPLAY: block; HEIGHT: 246px; CURSOR: hand" id="BLOGGER_PHOTO_ID_5529835746052944770" border="0" alt="" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgfiNkChYOg0t0bg09Or7XSFdz4ZW2KXInTnMZuswJHK2TGkR2qHrBwfCm7NgYFVZ5JgTwZZtp97PvWOLUcQoC_zfSjh952oPJPEvIZ5RGTc6ipJ-pYXpnfjN4fmP9fKSebk8xybRTs9pY/s320/wq.gif" /> <div>Anthony worked on the problem of <span style="FONT-WEIGHT: bold">replica exchange</span>, which is a technique for running molecular simulations in parallel at different energy levels, in order to achieve a more rapid exploration of the energy landscape. Our friends in the Laboratory for Computational Life Sciences down the hall have developed a molecular dynamics engine known as <a href="http://protomol.sourceforge.net/">Protomol</a>, and then implemented replica exchange using MPI. Anthony put Protomol and Work Queue together to create an implementation of replica exchange that can run on an arbitrary number of processors, and demonstrated it running on Condor and SGE simultaneously hundreds of nodes. What's even better is that the computation kernel was simply the sequential version of Protomol, so we avoided all of the software engineering headaches that would come with changing the base software.<br /><br />Zachary worked with the <span style="FONT-WEIGHT: bold">genome annotation tool</span> Maker, which is used to do things like finding protein sequences within an existing genome. Maker was already parallelized using Perl-MPI, so this required Zach to do some reverse engineering to get at the basic algorithm. However, it became clear that the MPI aspect was simply doling out work units to each node, with the additional optimization of work stealing. Zach added a Perl interface to Work Queue, and converted Maker into an elastic application running on hundreds of nodes. We are currently integrating Maker into Biocompute, our local bioinformatics portal.</div><div> </div><div>Speaking of <a href="http://biocompute.cse.nd.edu/">Biocompute</a>, Notre Dame student Brian Kachmarck did a nice job this summer of re-working the user interface to the web site. Not only is it faster and more visually appealing, it also does a better job of presenting the Data-Action-Queue concept described in our recent <a href="http://portal.acm.org/citation.cfm?id=1851476.1851547">paper about the system</a>. </div><br /><br /><img style="TEXT-ALIGN: center; MARGIN: 0px auto 10px; WIDTH: 380px; DISPLAY: block; HEIGHT: 237px; CURSOR: hand" id="BLOGGER_PHOTO_ID_5529834420459814994" border="0" alt="" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhOV7AWn-oStznJg4yofnbdE8FhZoXE6ILdJpqlzBe8Dz0DdjnteoetgSokyUuzeVo-nGkx6cSiAP2i291NBOc71k6lToEpdOfJ3FGgALssHVDwb9nKnZQM40fvRHNH5pIwt_p__m6BXEA/s320/Noname.png" /></div>Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com2tag:blogger.com,1999:blog-4890039722003127341.post-39740630464369125252010-04-05T12:45:00.000-04:002010-04-05T12:47:14.415-04:00The Forty Tribes of LinuxAs I have noted in this column before, a perennial challenge of distributed computing in the real world is dealing with the multiplicity of operating systems and related environments. If you are dealing with an uncontrolled environment like a large university or an 'at home' computing environment, there is no telling what you are going to get. If you have a piece of software that depends exactly on the presence of Linux 19.5.3.4.9.2, it just isn't going to work.<br /><br />You might think that this could be avoided by having a professionally managed environment. At Notre Dame, we have a site license for Red Hat Linux, and our staff are pretty rigorous in keeping everything up to date and on track. But even then, you can't assume everything is identical: there is no way to upgrade everyone simultaneously, and every machine operates on a different schedule (and discipline) for picking up automatic updates. For example, we are currently in the tail of of a general campus migration from Red Hat 4 to Red Hat 5.<br /><br />Here is some hard evidence. We recently started using the neat 'cron' feature in Condor to make a daily observation of the operating system version, kernel version, and C library version of each machine. With a few variations on condor_status, we can see the upgrade status of the whole system:<br /><br />The major release numbers (below) aren't too bad. About 3/4 of our cores are running the latest Red Hat, but another 73 machines are behind by a version or two. And, oops, looks like someone plugged in their own personal CentOS machine. Not too hard to deal with, if you are careful to put 'redhat_version' in your requirements:<br /><br /><pre><br />% condor_status -format "%s\n" redhat_version | sort | uniq -c | sort -rn<br /><br />782 Red Hat Enterprise Linux Server release 5.4 (Tikanga)<br />27 Red Hat Enterprise Linux AS release 4 (Nahant Update 7)<br />26 Red Hat Enterprise Linux Server release 5.3 (Tikanga)<br />10 Red Hat Enterprise Linux AS release 4 (Nahant Update 8)<br />10 Red Hat Enterprise Linux WS release 4 (Nahant Update 7)<br />4 CentOS release 5.3 (Final)<br /></pre><br /><br />If we go a little deeper, the picture gets murkier. Below are the distribution of Linux kernel versions. Interesting to note that a few are hand-modified for some unusual hardware, and only two are Xen virtualized. Hope that you don't have any code sensitive to the kernel version.<br /><br /><pre><br />% condor_status -format "%s\n" kernel_version | sort | uniq -c | sort -rn<br /> <br />342 2.6.18-164.9.1.el5<br />294 2.6.18-164.el5<br />94 2.6.18-164.10.1.el5<br />32 2.6.18-164.11.1.el5<br />32 2.6.9-78.0.13.ELsmp<br />14 2.6.18-128.7.1.el5<br />12 2.6.18-164.6.1.el5<br />10 2.6.18-128.2.1.el5<br />6 2.6.18-164.2.1.el5<br />5 2.6.9-78.0.17.ELsmp<br />4 2.6.27.8-md-microway<br />4 2.6.9-89.0.20.ELsmp<br />2 2.6.18-128.4.1.el5<br />2 2.6.18-164.9.1.el5xen<br />2 2.6.9-78.0.5.ELsmp<br />2 2.6.9-89.0.16.ELsmp<br />2 2.6.9-89.0.9.ELsmp<br /></pre><br /><br />For completeness, here is the distribution of glibc versions, which has much the same story:<br /><br /><pre><br />% condor_status -format "%s\n" glibc_version | sort | uniq -c<br /><br />452 glibc-2.5-42.el5_4.2<br />296 glibc-2.5-42<br />34 glibc-2.5-42.el5_4.3<br />24 glibc-2.3.4-2.41<br />16 glibc-2.5-34.el5_3.1<br />14 glibc-2.5-34<br />13 glibc-2.3.4-2.41.el4_7.1<br />6 glibc-2.3.4-2.43<br />4 glibc-2.3.4-2.43.el4_8.1<br /></pre><br /> <br />In the good old days, you could just indicate that a program required OpSys=="LINUX" and more or less expect it to run. That certainly isn't possible now. Perhaps we are misleading users by talking about this thing called Linux, which doesn't really exist in any consistent form. Instead, we should be telling our users that a new operating system gets invented every week, and is usually named after a team on Survivor.<br /><br />The good folks at Sun tried to solve this problem almost 20 years ago with Java. The idea was that they would create a stable platform that could be implemented on any machine. Then, you could write programs that would be universally portable. The problem was, well...<br /><br /><pre><br />% condor_status -format "%s " JavaVendor -format "%s\n" JavaVersion | sort | uniq -c | sort -rn<br />308 Sun Microsystems Inc. 1.6.0<br />222 Sun Microsystems Inc. 1.6.0_15<br />174 Sun Microsystems Inc. 1.6.0_17<br />52 Free Software Foundation, Inc. 1.4.2<br />28 Sun Microsystems Inc. 1.6.0_18<br />3 Sun Microsystems Inc. 1.5.0_17<br />2 Apple Computer, Inc. 1.5.0_19<br /></pre><br /><br />Many people think the grand solution to this problem is virtual machines. Perhaps, but more on that next time.Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com0tag:blogger.com,1999:blog-4890039722003127341.post-85650972351584605882010-01-21T13:37:00.001-05:002010-01-21T13:39:06.906-05:00Summer REU at Notre DameWe invite outstanding undergraduates to apply for summer research<br />positions in scientific and cloud computing at the University of Notre Dame.<br />Students will build and operate systems that harness hundreds of<br />machines at once to attack large problems in science and engineering.<br /><br />Research topics include:<br /><ul><li>Green Cloud Computing</li><li> Portals for Scientific Research</li><li> Languages for Distributed Computing</li></ul> More information is available here:<br /><br /><a href="http://www.cse.nd.edu/%7Eccl/reu/2010/" target="_blank">http://www.cse.nd.edu/~ccl/<wbr>reu/2010/</a><br /><br />Applications received by March 1st will be given first consideration.Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com2tag:blogger.com,1999:blog-4890039722003127341.post-74893424117170637662010-01-11T11:07:00.006-05:002010-01-11T12:29:09.141-05:00Green Cloud OnlineThe Green Cloud is now online!<br /><br />The Green Cloud is the invention of Dr. Paul Brenner at the ND Center for Research Computing. It is a containerized data center located at the South Bend city greenhouse, stocked with used servers kindly donated by Ebay, Inc. The first batch of machines was installed in December, and will eventually reach about 400 cores once everything is turned on.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg20pz2TAtgk9pLWw6chmzeuzavpLMovII0tjuwiO74R_IMKdAooV7bOowxqoU2AjD4tKv1OW3ca-UEr91iFv1Z-s-D_F8Pnab6N2KjO9k-7jPE8ifpi9e76CFekWhFvRGLcWRGyk6A7sk/s1600-h/greencloud.gif"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 285px; height: 189px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg20pz2TAtgk9pLWw6chmzeuzavpLMovII0tjuwiO74R_IMKdAooV7bOowxqoU2AjD4tKv1OW3ca-UEr91iFv1Z-s-D_F8Pnab6N2KjO9k-7jPE8ifpi9e76CFekWhFvRGLcWRGyk6A7sk/s320/greencloud.gif" alt="" id="BLOGGER_PHOTO_ID_5425535102693714514" border="0" /></a><br />What makes the data center unique is that is has <span style="font-weight: bold;">no air conditioning</span>. Instead, the data center takes in ambient air, and then exhausts it into the greenhouse. This benefits Notre Dame, since we no longer pay the cost of cooling, but it also benefits the greenhouse, which has significant heating costs during the winter months. (We used to call this idea <a href="http://dthain.blogspot.com/2009/06/grid-heating-putting-data-center-heat.html">grid heating</a>.)<br /><br />Of course, this means the capacity of the system may change with the weather. During the winter, the system can run at full blast and deliver as much heat as possible to the greenhouse. During the spring and fall, the heat may not be needed, and can be vented outdoors. During the hottest part of the summer, we may need to shut some machines down to get the temperature under control. However, recent studies by big data center operators suggest that machine temperature could be safely increased to 80 or 90 degrees, so there may be a fair amount of headroom available. We will see.<br /><br />For a normal data center that runs web servers and databases, shutting down machines is not really an option. However, the Green Cloud provides fungible computing power for large computations in science and engineering at Notre Dame. If structured correctly, these workloads can adapt to 10 or 100 or 1000 cores. So, turning machines on and off will affect performance, but not correctness.<br /><br />A good example of a flexible workload is genome assembly. Two of our students, Christopher Moretti and Michael Olson presented initial results on a <a href="http://www.cse.nd.edu/%7Eccl/research/papers/assembly-mtags09.pdf">Scalable Genome Assembler</a> at the <a href="http://dsl.cs.uchicago.edu/MTAGS09/">MTAGS Workshop</a> held at <a href="http://www.sc09.org/">Supercomputing 2009</a>. Their assembler uses our <a href="http://www.cse.nd.edu/%7Eccl/software/workqueue">Work Queue</a> framework to manage a variable workforce, pushing out sequence fragments to whatever machines are available. The system has scaled up to about 1000 cores, spread across the Notre Dame campus, the Green Cloud, Purdue University, and the University of Wisconsin.<br /><br />We are currently working on a journal paper and an open source release of the assembler, so stay tuned for details.Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com1tag:blogger.com,1999:blog-4890039722003127341.post-72199086661500460942009-10-08T09:00:00.000-04:002009-10-08T09:00:04.815-04:00On Programming With Processes, Part II<div>One of the biggest challenges in building computer systems is finding a way to make things <strong>simpler</strong>. Any propeller-head can make a piece of software more complicated. Unfortunately, our industry seems to have a way of gravitating toward the complex. Let's look at the current state of the web browsers -- pick any one -- which seem to insist upon reimplementing or otherwise abusing the operating system. </div><br /><div><span style="font-weight: bold;">Exhibit 1</span>: About 2003, tabbed browsing is heralded as the wave of the future, and every web browser re-writes itself from scratch to support tabs and issues gushing press releases. What is a tab? Well, it's a way to switch between multiple running programs, each with its own title and visual space. Which is to say... it's like having windows! Except it's worse than having windows, it's like the old awful <a href="http://msdn.microsoft.com/en-us/library/ms632591%28VS.85%29.aspx">Multiple Document Interface</a>, which even Microsoft now admits confused the heck out of everyone.</div><br /><div>The funny thing is, you can achieve exactly the same behavior by dragging your taskbar to the top of the screen, like this:<br /></div><br /><div><img style="margin: 0px auto 10px; text-align: center; width: 400px; display: block; height: 202px;" id="BLOGGER_PHOTO_ID_5358497584674542210" alt="" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgeAoJkA0egOEJsjKrLBGNVwK4-A3rO2M4TP4pUiPwVCCz8xADya3DVHcH9jG0hOLxSDLpDXDrgSItEQaOQx7OlFNH6gFpermZ3IK-Pgg9z9T_FYoe2_0HaCkTkNAmp_Pp5gftNypdzOTo/s400/tabbed-browsing.gif" border="0" /> <span style="font-weight: bold;">Exhibit 2</span>: You cannot run the latest version of Netscape (a.k.a Mozilla, Firefox, SeaMonkey, IceWeasel, good grief...) <a href="http://www.google.com/search?q=firefox+nfs+home">if your home directory is on a distributed file system</a>. Never mind that putting your home directory on a shared filesystem is <span style="font-weight: bold;">the normal practice in 90% of the industrialized worl</span><span style="font-weight: bold;">d</span>, where the user of the machine works for an organization that keeps important documents on a central server.<br /><br />Apparently, Firefox uses an embedded database to store your preferences, bookmarks, cache, etc, and it cannot tolerate multiple simultaneous access. So, if you try to run multiple instances at once, it has to be clever enough to find the running copy and tell it to open a new window. If it cannot find it because the other copy is running in another console or on another machine, you get this ridiculous message: </div><br /><div></div><br /><div><img style="margin: 0px auto 10px; text-align: center; width: 400px; display: block; height: 85px;" id="BLOGGER_PHOTO_ID_5387364187161962754" alt="" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZ4_rUV1pdL0_CAo2FSgVIoMBU2hcd1blsjIwiRa5SXhBw0p9tQNKz5T39fGygFFh4IyfKKbwbwI9sB06E4wO9VnBh-H4hacbXXhh3RhITxmeLDzdy6R8_blv7mrE-ZwcnFdYjRe7FmYw/s400/error.gif" border="0" /><br /><p><span style="font-weight: bold;">Exhibit 3: </span>Google Chrome is supposed to be the re-invention of the web browser, except simpler and more robust. Instead of threads, it uses this new-fangled technology called "processes" instead of those old gnarly threads. So far, so good. Then Firefox decides to get on this bandwagon.</p><p>Unfortunately, Firefox is <span style="font-weight: bold;">missing the point entirely</span>. The plan is to break the UI that controls <strong>all the windows</strong> into one process, and the plugins, parsers, renderers, etc into separate processes. It should come as no surprise that this makes things <a href="https://wiki.mozilla.org/Content_Processes">even more complicated</a>, because the various pieces have to communicate with each other. More subtly, it makes the failure semantics really strange: if a helper process dies, one window will fail, but if the UI process dies, a whole bunch of windows will fail. If you look at the set of running processes, you are going to see an unpredictable number of processes with names that have no relation to what you are actually doing.</p><p>Everyone seems to have missed a ridiculously simple solution to all of these problems: <strong>Run each browser window in a separate process</strong>. You don't have to separate out all of the complex plugins, renderers, and so forth, because if one crashes, it will only take down that window. Furthermore, to open a new browser page in any context, all you have to do is fork() and exec("browser http://") and the operating system takes care of the rest.</p><p>See also: <a href="http://dthain.blogspot.com/2009/02/on-parallel-programming-with-processes.html">On Parallel Programming with Processes</a></p></div>Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com8tag:blogger.com,1999:blog-4890039722003127341.post-12038568536429045172009-10-01T23:00:00.001-04:002009-10-01T23:08:47.991-04:00Partly Cloudy with a Chance of Condor<div> </div><div>We have been thinking about cloud computing quite a bit over the last month. As I noted <a href="http://dthain.blogspot.com/2008/12/abstractions-grids-and-clouds-at-ieee-e.html">earlier</a>, cloud computing is hardly a new idea, but it does add a few new twists on some old concepts in distributed systems. So, we are spending some time to understand how we can take our existing big applications and make them work with cloud systems and software. It should come as no surprise that there are a number of ways to use <a href="http://www.cs.wisc.edu/condor">Condor</a> to harness clouds for big applications.</div><div> </div><div>Two weeks ago, I gave a talk titled <a href="http://www.cse.nd.edu/~dthain/talks/thain-geoclouds09.ppt">Science in the Clouds </a>at an NSF workshop on <a href="http://www.dataandsearch.org/dsi/events/geoclouds.html">Cloud Computing and the Geosciences</a>. One of the points that I made was that although clouds make it easy to allocate new machines that have exactly the environment you want, they don't solve the problem of work management. That is, if you have one million tasks to do, how do you reliably distribute them between your workstation, your campus computer center, and your cloud workforce? For this, you need some kind of job execution system, which is largely what grid computing has focused on:<br /></div><img style="TEXT-ALIGN: center; MARGIN: 0px auto 10px; WIDTH: 320px; DISPLAY: block; HEIGHT: 240px; CURSOR: hand" id="BLOGGER_PHOTO_ID_5387643321932435986" border="0" alt="" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjRZYX7vGqFKgNy2Ew53HMxl_A7dhVoVdvhPAGysRqO5WUNfu0PScMTHWZ-NO8jLuoOaL-8aY4EMs-Lm0Sj5XWd3NN995TYr_x6oiv5Im0E6wne8sL0LlJHuPbOd97gVAPPK7C-zGm4wbg/s320/cloud-grid1.gif" /><br /><div>As it stands, Condor is pretty good at managing work across multiple different kinds of systems. In fact, today you can go to a commercial service like <a href="http://www.cyclecomputing.com/">Cycle Computing</a>, who can build an on-demand Condor pool by allocating machines from Amazon: </div><br /><div></div><img style="TEXT-ALIGN: center; MARGIN: 0px auto 10px; WIDTH: 320px; DISPLAY: block; HEIGHT: 240px; CURSOR: hand" id="BLOGGER_PHOTO_ID_5387643394646470786" border="0" alt="" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi3d1OHV7ndmUyzTAObiWdQcvXxDnQi4l0lvya_MyaeUl3Y-ot9CMFkV_SS4bi6XsyqNd4ZRymvik2zkUG1JUNmko_tR1mfR7YsEHSrqSOU0rUGn_bnbt9wkaE2tqZUqrxpW0L1voTl0ec/s320/cloud-grid2.gif" /><br />Just today, we hosted Dhruba Borthakur at Notre Dame. Dhruba is the project lead for the open source <a href="http://hadoop.apache.org/">Apache Hadoop</a> system. We are cooking up some neat ways for Condor and Hadoop to play together. As a first step, one of my students Peter Bui has cooked up a module for <a href="http://www.cse.nd.edu/~ccl/software/parrot">Parrot</a> that talks to HDFS, the Hadoop file system. This allows any Unix program -- not just Java -- talk to HDFS, without requiring the kernel configuration and other headaches of using FUSE. Then, you can submit your jobs into a Condor pool and allow them to access data in HDFS as if it were a local file system. The next step is to co-locate the Condor jobs with the Hadoop data that they want to access. <img style="TEXT-ALIGN: center; MARGIN: 0px auto 10px; WIDTH: 320px; DISPLAY: block; HEIGHT: 240px; CURSOR: hand" id="BLOGGER_PHOTO_ID_5387643469424625522" border="0" alt="" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgvJlnBWQc8jPg5RbYa98QuRuiGIAqoX37ax7o1XkvYsdKHPlVbGnKvrscCcg6TJPZ0_gjHoux9QCU8407BRN3CfUhhUdtsbOTpgGRDBbUdFvD7I2x-yanXy0PIY_ebA_wfYQj2S28Ejlk/s320/condor-parrot-hadoop.gif" /><br />Finally, if you are interested in cloud computing, you should attend CCA09 - <a href="http://www.cca09.org/">Cloud Computing and Applications </a>- to be held in Chicago on October 20th. This will be a focused, one day meeting with speakers from industry, academia who are both building and using cloud computers.Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com0tag:blogger.com,1999:blog-4890039722003127341.post-4930699428662770402009-08-03T09:00:00.001-04:002009-08-03T09:00:05.393-04:00REU Project: BXGridThis post continues last week's subject of summer REU projects.<br /><br />Rachel Witty and Kameron Srimoungchanh worked on <a href="http://dthain.blogspot.com/2008/12/bxgrid-biometrics-research-grid.html">BXGrid</a>, our web portal and computing system for biometrics research. This project is a collaboration between the <a href="http://www.cse.nd.edu/%7Eccl">Cooperative Computing Lab</a> and the <a href="http://www.cse.nd.edu/%7Ecvrl">Computer Vision Research Lab</a> at Notre Dame. Hoang Bui is the lead graduate student on the project. Rachel and Kameron added a bunch of new capabilities to the system; I'll show three examples today. <div><div><br />The first is the ability to handle 3-D face scans taken by a specialized camera equipped with a laser rangefinder. The still picture here doesn't quite do it justice, because each white "mask" on the left is a rotating animation of the face. By integrating this data into BXGrid, the 3-D data can be validated against previous ordinary images of the face.</div><div> </div></div><div><img style="margin: 0px auto 10px; text-align: center; width: 400px; display: block; height: 322px;" id="BLOGGER_PHOTO_ID_5363546501531331106" alt="" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhpKI9veVqaRbVQx2FxxsUWsIKxPAOywh6HiVeZVm3zpy8suQy_-9VwxFDDxvDKuXdpuDH__vlwFh23vI1G_zAU6iZMwOaoi9VIJR9KOwF6DquOIH2r9kKp5dy7a2BWntrTCAdnZe83txs/s400/bxgrid1.gif" border="0" /><br /><div>I previously discussed <a href="http://dthain.blogspot.com/2008/10/abstractions-for-distributed-computing.html">All-Pairs</a> problems, which are common in biometrics. While we already had the ability to run very large All-Pairs, problems, we never had the capability to view the results easily. Now, with the click of a button, you can set up a small All-Pairs problem and view the results on the portal:</div><br /><img style="margin: 0px auto 10px; text-align: center; width: 400px; display: block; height: 327px;" id="BLOGGER_PHOTO_ID_5363546319350178594" alt="" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjPhkgfzwZISBx8h0mmLEK6RDUYqz6DlJ2N7WpjxQ6tK1gVyZKAdp97cOuGNAhhzutAfeu8AQJUniq-naN75Lzs2JufDxbmw25cOm19p5ZZkI4QP0AKZ8zw75ZAT-RJ59gju7wUEgwY9dE/s400/bxgrid2.gif" border="0" /><br /><div>Currently, new data ingested into the system is validated manually by people who must visually check that a eye, face, or whatever matches existing data in the system. Although this can be divided up among a large team of people, it is still time consuming and error prone.<br /><br /></div><div> </div><div>Kameron and Rachel built a system that does a first pass at this task automatically. Using <a href="http://dthain.blogspot.com/2009/07/make-as-abstraction-for-distributed.html">Makeflow</a>, they set up a system to export all newly ingested images along with five good images that should match. This results in thousands of jobs sent to our Condor pool, which transform and compare the images. When all the results come back, you get a nice web page that summarizes the images and the results:</div><br /><img style="margin: 0px auto 10px; text-align: center; width: 400px; display: block; height: 382px;" id="BLOGGER_PHOTO_ID_5363546076958958434" alt="" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg8OyL32YNcKtRZ3ivRc6Uq8JrwX_s8RP_zEr0i-XZdST5FUV6AMXDka68zGV-YEXXyMDrE3flFl4aDOqM-g41e5UMdadxQ69jAEVWtxljnyHXnRZjfB2kBNRrdz7RoDbDa4H5C_BilFwI/s400/bxgrid3.gif" border="0" /><br /><div>This research was supported in part by the National Science Foundation via grant NSF-CCF-0621434.</div><div> </div></div>Douglas Thainhttp://www.blogger.com/profile/10046446527813216338noreply@blogger.com0