EDITOR'S EYE

The World of Software Development.

February 2007

So if you were tasked with selecting the "most influential computer-science paper of the decade," where would you begin? (Let me make it easier -- you could start by eliminating anything that has my name attached to it.) Give up? So let's narrow the scope to, say, the most influential machine vision paper of the decade. Any ideas?

Okay, how about Gerard Medioni's 1996 paper "Using Computer Vision in Real Applications: Two Success Stories" presented at the International Association of Pattern Recognition Workshop on Application of Computer Vision, Tokyo, Japan in November 1996.

If this was your guess, then you're right on target. Medioni, who is chair of the Viterbi School department of computer science at the University of Southern California, has been awarded the "Most Influential Paper of the Decade" award from his peers in the machine-vision world for the classic paper he presented 11 years ago.

Back in the late 1990s, Gerard Medioni was engaged computer-vision research that led to, among other applications, techniques now used to integrate images into live video, so that viewers of a football game can see the line that must be crossed to get a first down.

The work grew out of algorithms Medioni created that let computers recognize objects in video, first looking for edges, then using those edges to define shapes, and then to recognize those shapes when viewed from different angles.

The breakthrough -- for which he is now being recognized -- came when he began to use the same algorithms to guide computers in creating images instead of interpreting them. In addition to the ability to insert images in live video, other applications included:

• A 3-D pen that lets visual designers create and mold 3-D shapes in a single step, rather than by the traditional means of using many 2-D renderings. The same device can "trace" existing objects in three dimensions to scan them into computers.
• A way to combine a minimal number of 2-D photographic views to create virtual 3-D objects, or even virtual environments.

Congratulations to Professor Medioni for a job well done.

Editor's Note: Professor Medioni has graciously made an early version of his paper available. You can read it here.

Posted by Jon Erickson at 10:41 AM  Permalink |

Every year, the list of things I'd like to accomplish gets longer, not shorter. Let's see: Rebuild an automobile motor (check, done that). Write a book (check, done that). Build a house (check, done that). Learn sign language (not yet, next year). Ride a motor scooter in Hyderabad (scratch that, not even on a bet). Learn lip-reading (not yet, next year). You get the idea.

As it turns out, researchers at the University of East Anglia in the UK are a step ahead of me and just might help me out. Led by Richard Harvey, a senior lecturer at UEA’s School of Computing Sciences, a research team is hopes to develop computer lip-reading systems that could be used for fighting crime, among other applications. The three-year project will collect data for lip-reading and use it to create machines that automatically convert videos of lip-motions into text. It builds on work already carried out at UEA to develop state-of-the-art speech reading systems.

"We all lip read, for example in noisy situations like a bar or party, but even the performance of expert lip readers can be very poor," Harvey says. "It appears that the best lip-readers are the ones who learned to speak a language before they lost their hearing and who have been taught lip-reading intensively. It is a very desirable skill."

Harvey is teaming up with the Centre for Vision, Speech and Signal Processing at Surrey University, which has built accurate and reliable face and lip trackers, and the Home Office Scientific Development Branch, which wants to investigate the feasibility of using the technology for crime fighting. According to Harvey, "The Home Office Scientific Development Branch is interested in anything that helps the police gather information about criminals or gather evidence."

Another reason for developing computerized lip-reading is that the number of trained lip-readers is falling, mainly because people tend to be taught to sign instead.

As for my interest, I'd bet that some interesting learning software will come out of this research -- software that I'll get to right after I climb a mountain somewhere.

Posted by Jon Erickson at 01:24 PM  Permalink |

If you can't believe fiction, what can you believe? Thanks to computers, two movies -- "Poseidon" and "Pirates of the Caribbean: Dead Man's Chest" -- nominated for a special effects Oscar at this year's Academy Award benefited from heavy numerical simulation, at least according to Ron Fedkiw, an assistant professor of computer science at Stanford University and consultant to Industrial Light and Magic.

In a presentation at the annual meeting of the American Association for the Advancement of Science, Fedkiw took film lovers behind the scenes of today's movies in his discussions of physics-based simulations the lend realism to to fantasy.

"It is an exhaustive task to prescribe the motion of every degree of freedom in a piece of clothing or a crashing wave," says Fedkiw. "Since these motions are governed by physical processes, it can be difficult to make these phenomena appear natural. Thus, physically based simulation has become quite popular in the special effects industry. The same class of tools useful for computational fluid dynamics is also useful for sinking a ship on the big screen."

But until recently, computer graphics experts could run inferior algorithms on many processors, or run the best algorithm on only one processor. The problem is that many algorithms do not scale well to larger numbers of processors. But about a year and a half ago, Fedkiw figured out how to run a star algorithm on many processors, resulting in special effects and stunning realism.

These days, Fedkiw designs new algorithms for diverse applications including computational fluid dynamics and solid mechanics, computer graphics, computer vision, and computational biomechanics. The algorithms may rotate objects, simulate textures, generate reflections or mimic collisions. Or they may mathematically stitch together slices of a falling water drop, rising smoke wisp or flickering flame to weave realism into computer graphic images.

"The simulation of gases, liquids and combustion for scientific reasons quickly translates into the ability to make animations of smoke, water and fire," Fedkiw says. "Similar statements hold for soft biological tissues, muscles, fractures and other solid material problems. Once the scientific numerical simulations are worked out, interesting animations can be made shortly thereafter."

As an aside, I have to report that in a true-life brush-with-glory moment, I've actually seen -- not one -- but two real Oscars. The story goes like this: Years ago I was working for a computer-book publisher who had offices in the Fantasy Record building in Berkeley, California. Shlepping into the lobby on my way to lunch across the street at Juan's one day, the lobby was packed with people, ballons, and champagne. As luck would have it, Saul Zaentz and Milos Foreman also had offices and studios in the same building (Zaentz, in fact, owned the building which was referred to as "the house that Creedence built" because the band Creedence Clearwater Revival recorded their first hit record there.) The night before, Zaentz had just received that year's Best Picture Award for "Amadeus" and Foreman Best Director for the same movie. Having just returned from the Academy Awards, they were walking into the lobby as I was walking out. So I ended up holding the door for Zaentz and Foreman as they held the Oscars above their head -- and the packed lobby cheered. Come on, you really didn't think those ballons were for me?

Posted by Jon Erickson at 09:55 AM  Permalink |

We heard from Peter Meyer the other day, which is noteworthy because we haven't heard from him for, well, a long time. In fact, the last time Peter crossed our path he was living in California, doing research in AI, and heading up his one-man software shop selling his Dolphin C Toolkit and Dolphin Encrypt. Peter also wrote the famously popular Dr. Dobb's article Julian and Gregorian Calendars.

Peter is living in Switzerland now, but continues to write calendar-related software (as well as security and other programs), although Dolphin has been replaced by Hermetic Systems. In the process, he has extended his original research into the Gregorian and Julian calendars by developing Chinese Calendrics, a program for converting between dates in various Chinese calendars and dates in the Gregorian and Julian calendars, and to find (among other things) lunar New Year's day and leap months for any year in the Chinese Calendar. Old habits (and old calendars) are hard to break.

Interestingly, calendar reform is still a controversial topic, even if only in specialist circles. As Peter reports, there were two attempts at calendar reform under the League of Nations and the United Nations, but both failed because the proposed reform interrupted the 7-day week cycle (5-day and 6-day weeks were tried in Russia, but were abandoned). So only a reform which preserves the 7-day week has any chance of acceptance.

After leaving California for Europe in 1994, Peter spent a few years in the U.K. as a research student, when he wrote a large program in C to perform simulation of magnetic material. A programmer at heart, he says that the fun part was writing the software; the subject itself (and performing lots and lots of simulation runs) was of less interest. Still, it got Peter an M.Phil (his thesis is available online). After that (and more travelling)he did a stint as a research assistant at the University of Queensland, again writing C code, in the area of machine learning. Followed by an extended ramble through Asia, then back to Europe, where he continues to make a living by marketing his software.

He's also come up with a programming language called EDC, which is short for "Easy Date Converter". EDC not only processes date operations sequentially, it also allows date operations to be performed based on "program logic". It thus implements a programming language, though not one with all the features of the better-known programming languages. We'll be posting more on EDC before long.

So good to hear from you Peter. Maybe it is about time to start on your next Dr. Dobb's article.

Posted by Jon Erickson at 10:56 AM  Permalink |

There are transactional systems, and then there are TRANSACTIONAL SYSTEMS. The former we see everyday when we use a credit card to pay for some retail purchase. But it is the latter that knocks your socks off because of the sheer magnitude of the transactions.

A good example of the latter is the announcement by IBM and Financial Network Services who are claiming the world's largest core banking benchmark result, delivering a record 9,445 business transactions per second (tps) in real-time based on more than 380 million accounts with 3 billion transaction histories. That's a lot of transactions.

IBM and FNS worked with Bank of China on the scalability benchmark powered by an IBM System z9 Parallel Sysplex mainframe running DB2 database software and FNS's BANCS core banking application software.

The goal of the benchmark was to execute a range of tests that covered online transaction processing (OLTP) scalability, end-of-day batch processing, and end-of-month batch processing with a target of handling unprecedented transaction volumes. The transaction and account mix was based on real customer projected workload characteristics in their production environment: cash deposit, credit transaction, cash withdrawal, debit transaction, loan account inquiry, deposit account inquiry, loan repayment cash, and loan repayment credit transaction.

The benchmark was performed at IBM's System z Customer Benchmark Center in Poughkeepsie, New York, from June to August 2006. The solution was based on FNS's BANCS core banking software package running on two IBM System z9 Enterprise Class Model 2094 (S54-754) machines and four DS8300 model 2107-922 storage subsystems. IBM System z9 was allocated with over 30,000 MIPS and 52 TB of DASD running on z/OS with DB2 relational database software and a CICS/TS Environment. The FNS BANCS solution only utilized 85 percent capacity of MIPS and 35 percent of DASD for application data processing, revealing massive scalability, and optimum system performance.

Posted by Jon Erickson at 10:36 AM  Permalink |

IBM has launched a programming contest for college and university students. The contest seeks the most innovative applications written for the Cell Broadband Engine (Cell/B.E.).

The Cell/B.E is a multi-core device with nine processors on a single silicon die that was jointly designed by IBM, Sony, and Toshiba and used in the Playstation 3. It is really fast -- but it is also really difficult to program.

To have a shot at the $10,000 first-place prize ($2500 for the fourth-place winner), contest participants have to demonstrate mastery of the theoretical and practical uses of Cell/B.E. technologies. Students can complete an online quiz testing their knowledge of Cell/B.E. trivia (Challenge 1), or they can develop an innovative software program based on the technology -- and win a cash prize if their selection is chosen (Challenge 2).

"In today's global economy, the ability to apply advanced technology, engineering and business thinking in equal parts is a prerequisite for success," said Nick Donofrio, IBM Executive Vice President, Innovation and Technology. "This contest gives students a unique opportunity to take the technology underpinnings of the Cell Broadband Engine and then imagine what is possible given their own skills and interests. They are the earliest adopters of these advanced technologies and in the best position to see new opportunities to take full advantage of its capabilities."

To find out more about developing the Cell processor, watch for the article "Programming the Cell Processor" by Daniele Paolo Scarpazza, Oreste Villa, and Fabrizio Petrini, which will appear in the April 2007 issue of Dr. Dobb's Journal.

Posted by Jon Erickson at 04:13 PM  Permalink |

In comemmoration of the recent 40th (or is it 50th?) anniversary of the APL programming language, I recently wrote a short article entitled APL and Oranges. I was surprised by the mail I received which was more interesting and more informative than the original article.

For instance, there was this note from Devlin Gualtieri:

I enjoyed your editorial on APL in the February, 2007, issue of Dr. Dobb's Journal. I used APL in the early 1970s. It ran on an IBM 360, and then an IBM 370, while I was at Syracuse University. I enjoyed it enough to use it later while at Allied-Signal through a dialup service. I published an APL computer program for modeling of magnetic bubble materials ("Computer Program Description: SPECS," I.E.E.E. Trans. Magnetics MAG-16, 1440-1441 (1980)), but I haven't used it since.

It's true that a typical APL program resembles programs submitted for the Obfuscated C Contest. But it's also true that it functions as a nice mathematical calculator, since it's interpreted, and it preceded Mathematica in that respect. I write all my code in C, now, with brief excursions into other languages, but for some tasks I wish I still had APL.

Then there were those APL typeballs, like the one that Mark Dresser still owns (but which I bet is gathering dust):

I actually have one of those APL typeballs that was installed on an IBM 2741 Selectric Terminal I acquired as surplus many years ago while a student.

I never did end up doing much with the terminal. It had a serial interface that ran at 134.5 baud (not 110, not 150, but 134.5!) Allegedly this was based on a careful study that determined that this was as fast as the mechanics would go without excessive wear.

About the time I figured out how to slow it down to 110 baud that a standard UART could be made to talk to, CRT terminals became affordable and I got rid of the monstrosity but kept the typeball along with other curiosities like nixie tubes, mag core memory...

But does knowing APL make you an old programmer, wonders John Russo? No, but I bet it makes you a good programmer:

APL was one of the first languages that I used in a professional environment. I first used it on terminals that used paper instead of CRTs, then on special CRT terminals that supported APL and had the special characters on the keys. Finally, I moved to a PC that had a special chip so that I could get the APL characters. I had to memorize which character was associated with which letter because I had a regular keyboard. I didn't think that anyone used APL any more. Does this make me an old programmer?

Paul Tremblet had a lot to say -- about APL, the typeballs, and more:

Your column on APL tugged at my heartstrings. I first learned APL in 1970 on the IBM 1130. It was distributed as a Type II program. As a chemistry major studying physical chemistry, I found the language immensely useful in studying planes of symmetry as part of a course entitled "Chemical Application of Group Theory" (although, when asked in the cafeteria where we were headed next, we often answered "to group therapy").

You mentioned the selectric typeball. Now there was a marvel! Did you know that the physical position of the characters on the ball corresponded to a "tilt-rotate" code. Bits in the byte that represented the character determined how the ball was tilted/rotated relative to a reference point to position the ball so that the proper character hit the ribbon. If you examine a typeball (and if you don't have one lying around, maybe Michael Swaine does since he seems to enjoy the history of computing - you might even want to share this with him), you will notice that every upper case letter is 180 degrees away from its lower case counterpart. Examine it some more and the whole code set will become obvious. This, of course, was true only for the "normal" typeball. When it came to APL, all bets were off (although I'm sure there was some logic involved). If I remember correctly, the number of characters in the APL character set was greater than the number on the ball so some characters were formed by overstriking. I have this vague recollection of having to hold down a special "overstrike" key on the keyboard as I typed a two-character sequence (even more fun than using trigraphs to type C code on an EBCDIC terminal that did not have certain characters such as a square bracket or curly brace).

The last time I had actual experience with APL was in the 1980s when I was approached by one of the MVS systems maintenance programmers who was waving a piece of paper contained what he thought was output from a printer on drugs and asking what the heck it was. I told him it was APL (so now he though I was on drugs) and asked him where he got it. He replied that he had received it from IBM as a patch that he should apply to the Graphical Data Display Manager (GDDM) subsystem. To me, it made perfect sense that such a system should use APL. It did, after all, involve performing numerous operations on matrices; and things like matrix inversion, which in any other language is complex and ugly, is trivial in APL. The maintenance programmer in question, being accustomed to received patches as PTF or PUT tapes (or sometimes punched cards) was now puzzled over how exactly to apply the patch. When he asked me how and I told him he should simply type it in, he really was ready to send me off to the padded room. Fortunately, I knew we had some of those black-on-orange quad screen IBM terminals (forget the model number) and because I was curious by nature, I had discovered that they had selectable character sets and one of the available sets was APL. I reprogrammed one quad of his terminal. He was happy that the patch got applied. I was happy I got to play.

Jeff recalls doing coding on a Selectric typewriter. Do they even make those any more?

It was with interest I read your editorial on APL. Still working in the industry at age 66, I find little that references what was done back in the '60s -- other than rock-and-roll. I worked for IBM then and I can remember using APL to crunch statistical data arrays. APL handled it well with very little coding. Keeping the meaning of the symbols straight was sometimes a chore. And all the coding done on a Selectric typewriter. A lot has happened in the past 40 years to get us to where we are today. I think we forget about many of the tools that enable us today

And Larry Baker had to occasion to attend a very cool ACM session. Lucky guy.

I had the privilege of attending the first ACM SIGPLAN History of Programming Languages (HOPL) Conference, June 1-3, 1978. Not only did Ken Iverson talk about APL, John Backus discussed Fortran, Alan Perlis and Peter Naur discussed ALGOL (where Peter Naur acknowledged John Backus' contribution of the syntax definition notation, Backus Normal Form, which later came to be known as Backus-Naur Form after his additions to BNF for ALGOL), John McCarthy discussed Lisp, Jean Sammet discussed COBOL, Thomas Kurtz discussed BASIC, and Ralph Griswold discussed SNOBOL. Other languages were presented by either their authors or significant contributors, but those were the big one for me. (C, C++, and Ada weren't around long enough by that time to qualify for inclusion; they were included in the Second HOPL Conference in 1993. By the way, HOPL III is coming up in June, 2007.) Text of the papers and transcripts of the talks appeared in the ACM Monograph History of Programming Languages, edited by Richard L. Wexelblat, ISBN 0-12-745040-8. I'm not sure it is still in print.

Thanks to you all for contributing to the history of programming languages. Just think, in another 40 years people will be saying the same thing about Java, Ruby, Python, and other antiquated programming languages.

Posted by Jon Erickson at 11:17 AM  Permalink |

With the release of the Intergovernmental Panel on Climate Change 4th Assessment Report, even skeptics are acknowledging that global warming is heating up.

According to the 4th Assessment Report, we can expect rising oceans, warmer oceans, sea ice reduction, warmer winters, and the like, all thanks to human-derived greenhouse gases that are playing havoc with our climate. The 2007 report will be presented in four phases during the year, with the first phase focusing on physical evidence of global change

"We are now seeing, not merely predicting, effects of greenhouse warming on a scale and in ways that were not observable before," said Gabriele Hegerl, associate research professor at Duke University's Nicholas School of the Environment and Earth Sciences, who also co-authored a summary of the report for policymakers. Hegerl, a coordinating lead author of the IPCC report's chapter on "Understanding and Attributing Climate Change," goes on to say that "We've studied improved observations from land, sea and space, as well as better temperature reconstructions covering the last 1,000 years. Understanding the observations is really what this all is about. For instance, looking at the patterns of change in 20th-century temperatures, we can now distinguish between changes caused by greenhouse gases, man-made aerosols, variability in solar radiation and major volcanic eruptions."

As you might expect all of this obervation and modeling requires computing power -- and lots of it. To that end, the National Oceanic and Atmospheric Administration (NOAA) has activated its newest weather and climate supercomputers, increasing the computational might used for climate and weather forecasts by 320 percent. The IBM machines process 14 trillion calculations per second at maximum performance and ingest more than 240 million global observations daily. These computers also will process data from Constellation Observing System for Meteorology, Ionosphere and Climate (COSMIC) satellites, a series of six satellites launched in 2006.

"Better physics, better models, better data, and faster and more powerful supercomputing are the foundation for making better weather and climate forecasts," said Conrad C. Lautenbacher, undersecretary of commerce for oceans and atmosphere and NOAA administrator."

"One of the most fascinating things is that we see that changes have already happened or are happening now in more climate variables than just temperature," says Hegerl. "For instance, there have been observed changes in ocean temperatures, global rainfall and in circulation of the atmosphere. We now are beginning to understand that these changes occur at least partly in response to anthropogenic influences on climate. This allows us to better evaluate model simulations, which do simulate aspects of these changes, although not as successfully as they simulate changes in temperature."

Posted by Jon Erickson at 09:18 AM  Permalink |

What I like about the National Institute of Standards and Technology (NIST) is that the folks who work there are so busy. They're doing cool -- and important -- stuff all the time. Plus NIST has taken the lead on a lot of critical issues; the Advanced Encryption Standard (AES) comes to mind.

More recently, NIST has kept its crypto nose to the grindstone by planning a competition to develop one or more cryptographic "hash" algorithms to support and revise the current Secure Hash Standard (Federal Information Processing Standard 180-2). To get the ball rolling, NIST is looking for comments on its recently published draft minimum acceptability requirements, submission requirements and evaluation criteria for candidate algorithms.

According to NIST, hashing algorithms are mathematical procedures that take data, usually a message, and chop and combine it down into a much shorter number that is a "fingerprint" of the original data. Good hash algorithms have two features -- two different inputs are overwhelmingly likely to generate two different fingerprints, and given a specific fingerprint, there is no practical way of calculating a set of input data that will have the same fingerprint. Hash algorithms are used widely by the federal government and others in various applications, such as digital signatures and message authentication. FIPS 180-2 specifies five cryptographic hash algorithms -- SHA-1, SHA-224, SHA-256, SHA-384 and SHA-512. Because serious attacks have been reported in recent years against cryptographic hash algorithms, including SHA-1, NIST is preparing the groundwork for a more secure hash standard.

As if that isn't enough, NIST has issued A Profile for IPv6 in the U.S. Government --Version 1.0 a draft report to assist federal agencies in developing plans to acquire and deploy products that implement Internet Protocol version 6 (IPv6). The profile recommends IPv6 capabilities for common network devices, including hosts, routers, intrusion detection systems and firewalls, and includes a selection of IPv6 standards and specifications needed to meet the minimum operational requirements of most federal agencies.

Again according to NIST, the Internet Protocol (IP) -- actually a suite of protocols -- is an international communications standard that defines how and where information such as text, voice and video move across the Internet. IPv6 is the next generation IP developed in the 1990s to replace the current version which has been in use for more than 20 years. The IPv6 protocols offer several significant improvements over the current IPv4 protocols, including a vastly greater number of "addresses" and faster routing.

In 2005, the Office of Management and Budget advised federal agencies that they must upgrade or modify systems to handle IPv6 by June 2008. (See OMB memo.) The NIST profile was developed to help ensure that IPv6-enabled federal information systems are interoperable and secure, and also addresses how such systems can interoperate and co-exist with the current IPv4 systems. Agencies with unique information technology requirements are expected to use the NIST profile as a basis for further refined specifications and policies.

The draft report also includes findings from NIST's analysis of the current state of IPv6 standards, emerging commercial implementations and testing programs. NIST found that a core set of IPv6 standards have stabilized and viable commercial implementations are emerging. However, products currently are at varying levels of maturity and completeness. NIST also found that improved IPv6 security technologies and testing services are needed to ensure the safety of federal information systems using IPv6. Over the next year, NIST plans to develop guidelines for the secure adoption of IPv6 and develop a testing strategy for IPv6 for federal agencies.

Posted by Jon Erickson at 09:46 PM  Permalink |