EDITOR'S EYE

The World of Software Development.

July 2006

Some people might call it a hack. But to me the STI Cell is just dessert. Orginally designed by Sony, Toshiba, and IBM (the "STI" in "STI Cell") as the processor for Sony's Playstation 3 game console, the STI Cell is all of a sudden on track to be a building block for next-generation high-performance systems used in computational science.

To this end, computer scientists at Berkeley Labs are benchmarking the processor's performance in running several scientific-application kernels, then comparing its performance against other processor architectures.

"Overall results demonstrate the tremendous potential of the Cell architecture for scientific computations in terms of both raw performance and power efficiency," report researchers Samuel Williams, Leonid Oliker, Parry Husbands, Shoaib Kamil, Katherine Yelick, and John Shalf. "We also conclude that Cell's heterogeneous multicore implementation is inherently better suited to the [high-performance computing] environment than homogeneous commodity multicore processors."

Cell is a high-performance implementation of software-controlled memory hierarchy in conjunction with the considerable floating-point resources required for demanding numerical algorithms. Cell is different form conventional multiprocessor or multicore architectures. Instead of using identical cooperating processors, it uses a conventional high-performance PowerPC core that controls eight single-instruction, multiple-data cores called "synergistic processing elements" (SPEs), each of which contains a synergistic processing unit, a local memory, and a memory-flow controller.

In addition to its departure from mainstream general-purpose processor designs, Cell is interesting because the intended game market means it will be produced at high volume, making it cost-competitive with commodity central processor units. Moreover, the pace of commodity microprocessor clock rates is slowing as chip power demands increase, and these worrisome trends have motivated the community of computational scientists to consider alternatives like STI Cell.

Berkeley Lab researchers examined the use of the STI Cell processor as a building block for future high-end parallel systems by investigating performance across several key scientific computing kernels: dense matrix multiplication, sparse matrix vector multiplication, stencil computations on regular grids, and one-dimensional and two-dimensional fast Fourier transforms. According to the research team, the current implementation of Cell is noted for its extremely high-performance, single-precision (32-bit) floating point resources. The majority of scientific applications require double precision (64 bits), however. Although Cell's peak double-precision performance is still impressive compared to its commodity peers (eight SPEs running at 3.2 gigahertz mean 14.6 billion floating-point operations per second),the group showed how a design with modest hardware changes, which they named Cell+, could improve double-precision performance.

They developed a performance model for Cell and used it to show direct comparisons of Cell against the AMD Opteron, Intel Itanium 2, and Cray X1 architectures. The performance model was then used to guide implementation development that was run on IBM's Full System Simulator, in order to provide even more accurate performance estimates.

The researchers argue that Cell's three-level memory architecture, which decouples main memory accesses from computation and is explicitly managed by the software, provides several advantages over mainstream cache-based architectures. First, performance is more predictable, because the load time from an SPE's local store is constant. Second, long block transfers from off-chip DRAM (dynamic random access memory) can achieve a much higher percentage of memory bandwidth than individual cache-line loads. Finally, for predictable memory-access patterns, communication and computation can effectively be overlapped by careful scheduling in software.

On average, Cell is eight times faster and at least eight times more power-efficient than current Opteron and Itanium processors, despite the fact that Cell's peak double-precision performance is fourteen times slower than its peak single-precision performance. If Cell were to include at least one fully usable pipelined double-precision floating-point unit, as proposed in the Cell+ implementation, these performance advantages would easily double.

Games or HPC. Everyone is having fun with this processor.

Posted by Jon Erickson at 10:18 AM  Permalink |

From what I hear, the human auditory system makes up in quality what it lacks in quantity. And that's something computers haven't been able to catch up with--until now.

More specifically, humans have 200 million light receptors in their eyes, 10 to 20 million receptors for smell, but only 8000 dedicated to sound. Compensating for this discrepancy may help explain why the auditory system is the fastest and most precise of the five senses.

The challenge that Marcelo Magnasco, professor and head of the Mathematical Physics Laboratory at Rockefeller University, and Timothy Gardner, a former Rockefeller graduate student who is now a Burroughs Wellcome Fund fellow at MIT, saw was to get computers to process complex, rapidly changing sounds as fast and precise as the brain. To that end, they came up with a sound-analysis algorithm that’s far more nuanced at transforming sound into a visual representation than current methods. "This outperforms everything in the market as a general method of sound analysis," Magnasco says. And, he notes, it may be the same type of method the brain actually uses.

Their algorithm, described in the Proceedings of the National Academy of Sciences, reassigns a sound’s rate and frequency data into a set of points that they could make into a histogram. When they tested their technique against other sound-analysis programs, they found that it gave them a greater ability to tease out the sound they were interested in from the noise that surrounded it.

One fundamental observation enabled this improvement--they were able to visualize the areas in which there was no sound at all. They used white noise because it’s the most complex sound available, with exactly the same amount of energy at all frequency levels. When they plugged their algorithm into a computer, it reassigned each tone and plotted the data points on a graph in which the x-axis was time and the y-axis was frequency. The resulting histograms showed thin, froth-like images, each "bubble" encircling a blue spot. Each blue spot indicated a zero, or a moment during which there was no sound at a particular frequency. "There is a theorem, " Magnasco says, "that tells us that we can know what the sound was by knowing when there was no sound." In other words, their pictures were being determined not by where there was volume, but where there was silence.

"If you want to show that your analysis is a valid signal estimation method, you have to understand what a sound looks like when it’s embedded in noise," Magnasco says. So he added a constant tone beneath the white noise. That tone appeared in their histograms as a thin yellow band, bubble edges converging in a horizontal line that cut straight through the center of the froth. This, he says, proves that their algorithm is a viable method of analysis, and one that may be related to how the mammalian brain parses sound.

"The applications are immense, and can be used in most fields of science and technology," Magnasco says. And those applications aren’t limited to sound, either. It can be used for any kind of data in which a series of time points are juxtaposed with discrete frequencies that are important to pick up. Radar and sonar both depend on this kind of time-frequency analysis, as does speech-recognition software. Medical tests such as electroencephalograms (EEGs), which measure multiple, discrete brainwaves use it, too. Geologists use time-frequency data to determine the composition of the ground under a surveyor’s feet, and an angler’s fishfinder uses the method to determine the water’s depth and locate schools of fish. But current methods are far from exact, so the algorithm has plenty of potential opportunities. "If we were able to do extremely high-resolution time-frequency analysis, we’d get unbelievable amounts of information from technologies like radar, " Magnasco says. "With radar now, for instance, you’d be able to tell there was a helicopter. With this algorithm, you’d be able to pick out each one of its blades." With this algorithm, researchers could one day give computers the same acuity as human ears, and give cochlear implants the power of 8000 hair cells.

Posted by Jon Erickson at 09:31 AM  Permalink |

Maybe its the unbearably hot weather, the melting ice caps, devastating hurricanes, or freak tsunamis. Whatever. The point is that hi-tech is starting to take the environment seriously, especially when it comes to computer equipement.

To that end, the Green Electronics Council launched earlier this year a U.S. Environmental Protection Agency (EPA) funded project called the "Electronic Products Environmental Assessmet Tool" (EPEAT) to help purchasers rank computer desktops, laptops, and monitors based on their environmental attributes. The three-tiered EPEAT rating system includes 23 required criteria and 28 optional criteria. EPEAT products are identified as EPEAT-Bronze, EPEAT-Silver, or EPEAT-Gold, depending on the number of optional environmental criteria incorporated in the product.

This month, more than 60 desktop computers, laptops, and monitors from three manufacturers--Dell, HP, and CTL--were recognized as high-performance, environmentally friendly computer equipment. All of the products meet the new EPEAT "green" computer standard and they are listed online in the at EPEAT database.

All EPEAT-registered computers have reduced levels of cadmium, lead, and mercury to better protect human health. They are more energy efficient, which reduces emissions of climate changing greenhouse gases. They are also easier to upgrade and recycle. In fact, manufacturers must offer safe recycling options for the products when they are no longer useable.

According to the EPA, conservative estimates that over the next five years project that purchases of EPEAT registered computers will result in reductions of:

• More than 13 million pounds of Hazardous Waste
• More than 3 million pounds of Non-hazardous Waste
• More than 600,000 MWh of Energy--enough to power 6 million homes

According to the Green Electronics Council, EPEAT has also already been referenced in nearly $32 billion worth of computer contracts, including contracts issued by the Department of Defense, Department of Homeland Security, NASA, Minnesota, the Commonwealth of Massachusetts, the City of San Jose, California, Kaiser Permanente, and Premiere, a healthcare purchasing alliance with more than 1,500 hospitals and more than 41,000 other healthcare sites.

Posted by Jon Erickson at 10:00 AM  Permalink |

In an effort to determine how it can improve how it gets science and technology advice on important issues, the U.S. House of Representatives Science Committee played "Ask the Experts" yesterday in a day long "hearing."

To a man (or woman, whatever the case may be), the experts agreed that there is a gap in the type of science and technology advice that Congress currently receives. Specifically, the witnesses called for Congress to have access to in-depth reviews of policy options and their technical implications. As Dr. Jon Peha, co-editor of the book Science and Technology Advice for Congress and a Professor of Engineering and Public Policy at Carnegie Mellon University, put it "there is a fundamental gap in the information available to Congress. There is no consistent source of in-depth assessments that are balanced, complete, impartial, and produced at a time and in a format that is sensitive to the specific needs of Congress."

Of course, for more than 20 years, Congress did have a technology support office--the Office of Technology Assessment--which provided technology forecasting and assessment. Alas, it was defunded and eliminated in 1995 in part because, according to some in Congress, it delivered "redundant" information. Apparently members of Congress who supported the demise of OTA believed they could get better information from lobbyists and contractors, like those defense contractors who supplied former Congressman Duke Cunningham with technology information, among other stuff. Others in Congress felt that the kind of information they were getting didn't fit their political needs, so they opted to shoot the messenger--OTA, in this case. Rep. Rush Holt (D-NJ), who testified at the hearing, acknowledged the role of politics, stating that "although we would like to believe that the scientific and technical advice and assessment provided from outside remains politically neutral, this is not necessarily the case."

Whatever you think about the bureaucracies, you can't deny that the OTA was productive. With a staff of less than 200 people and a budget of under $22 million, the OTA was the smallest of the legislative branch's agencies, but published 755 details reports on issues ranging from medical policy to advanced computer technologies.

In any event, yesterday's lip service to accurate technology information involved heavy-weight scientists from the American Association for the Advancement of Science, the American Chemical Society, and the National Research Council, in addition to Peha.

• Albert Teich, Director of Science and Policy Programs at the AAAS, testified that , "universities and scientific societies, including AAAS, have expanded efforts to bring accurate scientific information to Congress through reports on policy-relevant topics, position statements and scientific briefings." He then added that shortcomings still exist within the system. "To sum up, information is not in short supply on Capitol Hill, but information is not knowledge," he said. "Credible sources are needed to provide timely analysis and synthesis of scientific and technical information as a foundation for Congressional decisions."
• Catherine Hunt, President-elect of the American Chemical Society, suggested, "Congress should consider establishing an in-house science and technology unit that supplements their capabilities and provides timely, thorough assessments for decisions on issues involving a wide range of science, engineering, and technology." She continued, "This unit could be housed in CRS [Congressional Research Service], GAO [Government Accountability Office], or stand alone as a congressional support agency."
• Peter Blair, Executive Director of the Division on Engineering and Physical Sciences at the National Research Council, raised the possibility of expanding the role of the National Academies to help fill the current gaps in information available to Congress. "The National Academies have enjoyed a longstanding and effective working relationship with Congress on even the most contentious issues," Blair said. "There are, no doubt, many characteristics of that relationship that could be improved, both to perform the traditional NRC [National Research Council] role more effectively and to provide some opportunities to expand that role." Dr. Blair went on to make the comparison that Congress, when considering legislative options, is like a homebuyer. Members might get advice from the equivalents of a real estate agent, the seller, and their friends, but they still needed to hire the equivalent of a trusted housing inspector to dig around on the issues.

Of course, the Executive Branch does have its own technology advice column, the Office of Science and Technology Policy, although it is generally acknowledged as being politically charged, something the OTA was originally chartered to avoid.

Posted by Jon Erickson at 09:05 AM  Permalink |

Sometimes brute force beats the pants off hi-tech. That's certainly appears to be the case with RFID clipped tag technology, also know as "privacy enhancing RFID tag."

Clipped tag technology lets you literally tear off a section of an RFID tag (essentially a tiny radio transmitter), thereby reducing the tag's read range to just a few inches with the ultimate goal of protecting your privacy in retail envirnoments while still maintaining the benefits of RFID technology. The tags may still be used after modification for returning items.

Figure 1: Schematic diagram of privacy-enhancing RFID tag (Clipped Tag). (Courtesy IBM.)

Developed at IBM's Watson Research Center, clipped tags have moved out of the lab and onto the manufacturing line at Marnlen RFiD where the high-speed RFID label converting equipment produces labels containing RFID.

Clipped tag technology is one of several approaches to addressing RFID privacy concerns in regards to item-level tagging. Another approach, proposed by RSA Labs, is the use of "Blocker Tags" that tags interfere with the reading of other RFID tags. See "RFID Blocker Tags" by Burt Kaliski for more information. For a description of how RFID is being used in some retail environments, listen to "RFID Means 'Smart Stores'".

For the most part, RFID tagging has been limited to warehouses and manufacturing sites, some companies are starting to use the technology on single items in the retail marketplace. An example of this is in the pharmaceutical industry--an industry which is known for its undying concern for consumer welfare (please note sarcasm here)--which says that it is RFID tags to help protect consumers from counterfeit drugs. Right.

Posted by Jon Erickson at 09:01 AM  Permalink |

Even though I've never been on the campus, let alone attended classes there, the University of Colorado at Boulder sounds like my kind of school.

In a clinical trial that will launch early next month, a group of volunteers to bed for 10 days in the name of science in an effort to understand and treat muscle atrophy. The subjects -- who will be between the ages of 18 and 45 -- will spend their days reading, chatting, watching videos, and surfing the Internet. Hmmm, that sounds pretty much like my college career, from what I recall.

The BioServe Space Technologies Center in CU's aerospace engineering sciences department will be examining the effects of a new experimental drug to mitigate muscle degeneration in 15 healthy adult males, says BioServe Director Louis Stodieck. The trial builds on a 2005 BioServe study of 10 men who remained prone for 10 days -- even for showers and bathroom breaks -- so researchers could chart molecular changes in their muscle tissue and better understand cellular pathways associated with muscle disuse. The study is funded in part by NASA and the National Institutes of Health.

Founded in 1987, BioServe works with a number of industrial partnerships and is one of 11 NASA Research Partnership Centers in the United States promoting the commercial development of space. Faculty, staff and students at BioServe have designed, built and flown 35 life sciences and biomedical research payloads on 24 space shuttle flights and on International Space Station missions. BioServe is slated to fly payloads on three of the next four NASA space shuttle missions beginning in late August, he said. Stodieck said the center hopes to fly a space shuttle experiment in 2007 involving mice to investigate new pharmaceuticals to treat muscle-wasting conditions.

Students elsewhere on the Boulder campus are a bit more ambitious, however. A team Colorado team was selected as the winners in the Mathematical Contest in Modeling (MCM) at The Society for Industrial and Applied Mathematics (SIAM) for their approach to solving the Continuous Problem: "Positioning and Moving Sprinkler Systems for Irrigation." The students are Brian Camley, Pascal Getreuer, Bradley Klingenberg and their faculty advisor Professor Bengt Fornberg. Their solution was titled "Sprinkle, Sprinkle, Little Yard."

Posted by Jon Erickson at 08:31 AM  Permalink |

The barber shop I go to is old school. A long, narrow room with yellowed newspaper clippings taped to the wall, an irritating 13-inch TV permanently set to ESPN, and a revolving barber pole on the sidewalk out front.

The shop only has two real concessions to the 21st Century. The 13-inch TV is color and copies of Dr. Dobb's Journal mysteriously appear every month, mixed in among the fishing and hunting magazines.

With this in mind, I'd be curious to know what makes Steve Marschner, an assistant professor of computer science at Cornell University, and Jonathan Moon, a Ph.D. student working with Marschner, experts in hair. Let's face it, a Ph.D. from Cornell is okay, but it isn't the same thing as a certificate from the Mystros Barber Academy or license from OG's School of Hair.

Still, Marschner and Moon know their hair. They know it so well, in fact, that they've come up with a new algorithm for more accurately simulating computer-generated hair.

Marschner and Moon's algorithm begins by tracing rays from the light source into the hair, using some approximations of the scattering and producing a map of where photons of light can be found throughout the volume of hair. Then it traces a ray from each pixel of the image to a point in the hair and looks at the map to decide how much light should be available there.

The result, in a test rendering of a swatch of blond hair, appears almost identical to a rendering by the laborious path-tracing method. Path tracing for the test required 60 hours of computation, while the new method took only 2.5 hours, the researchers report.

"The model that's been around since the '80s works for black hair, and a model we introduced in 2003 in collaboration with workers at Stanford gets brown hair right and makes blond hair better," said Marschner. "Using that model with our new work provides the first practical method to use physically realistic rendering for blond hair and still get the right color."

The problem is that light traveling through a mass of blond hair is not only reflected off the surfaces of the hairs, but passes through the hairs and emerges in a diffused form, from there to be reflected and transmitted some more.

The only method that can render this perfectly is "path-tracing," in which the computer works backward from each pixel of the image, calculating the path of each ray of light back to the original light source. Since this require hours of calculations, computer artists resort to approximations.

"People do something reasonable for one bounce and then assume it reflects diffusely," Marschner explained. In other words, he said, they assume that hair is opaque. "In light-colored hair it's important to keep track of the hair-to-hair scattering," he said.

Marschner now plans to look for better ways to generate the geometric model of hair that underlies the rendering and to simulate realistically the way hair moves. "Tools that generate hair generate random strands in space, and it's unclear whether the arrangement is realistic," he explained.

Actually, as you can tell from my accompanying photo, I have other concerns. Like now that Marschner and Moon can help me more realistically render hair, how about helping just grow it.

Posted by Jon Erickson at 08:55 AM  Permalink |

Yesterday was Chicago and Dr. Dobb's Architecture & Design Conference. Granted it is a four-day event (ending today) and I was only there one day. Still it was interesting, and I don't just mean taking the L-train from Midway Airport to the McCormick Place Convention Center.

Lots of good sessions on Wednesday, ranging from "Aspects in Dynamic Languages" to "Patterns for Service-Oriented Architecture." However, the highlight for me was Hugh Thompson's keynote on "Securing Software Design and Architecture: Uncut and Uncensored." What I didn't realize was that, for a mathematician, Hugh is a funny guy.

I know Hugh primarily from the security-related articles he's written for Dr. Dobb's, including the likes of:

• Testing for Software Security.
• When Format Strings Attack!.
• Rethinking Software Security.

as well as his best-selling books such as The Software Vulnerability Guide (reviewed here), and How to Break Software Security.

In his Wednesday keynote Hugh's focus was on the need to build security into applications. His point was that to do this, we have to start thinking like an abuser, instead of a user. That we have consider security requirement, not just of functional ones. And that security doesn't start and stop with just a firewall.

What did "uncut and uncensored" have to do with his talk? Much of his presentation dealt with real-world security lapses ranging from his shutting down in-air video on a commercial airplane, to manipulating cookies for doing end-arounds on faulty e-commerce implementations. Real world--and real scary at times.

Posted by Jon Erickson at 09:35 AM  Permalink |

I've had to explain it to the boss more than once. And finally, I have scientific backing. FreeCell, the Solitaire-like card game that comes with Windows (and elsewhere), is not a waste of time--it's therapeutic.

Okay, "therapeutic" may be stretching it a bit, considering that I've been busted three times this week for playing FreeCell at my desk. Maybe a better way of putting it is that I now consider myself part of a scientific research program like that at Oregon Health & Science University where researchers are monitoring cognitive changes in the elderly. What they've found is that when adapted with cognitive performance assessment algorithms, FreeCell may be able to distinguish between persons with memory problems and cognitively healthy seniors.

People with mild cognitive impairment are at high risk of developing dementia, which is most commonly caused by Alzheimer's disease. The discovery could help doctors plan early treatment strategies by detecting subtle cognitive changes over time in the natural setting of an elder's home.

"We discovered that we can take an existing computer game that people already have found enjoyable and extract cognitive assessment measures from it," said Holly Jimison, associate professor of medical informatics and clinical epidemiology and the study's lead author. Jimison and study co-author Misha Pavel, a professor of biomedical engineering and computer science and electrical engineering at OHSU's School of Science & Engineering, studied nine people with an average age of 80. All were regular computer users who played the FreeCell game frequently over a six-month period. Each participant was given a cognition score based on a brief battery of tests, and three were found to have mild cognitive impairment.

To measure cognitive performance, researchers compared each user's play efficiency to a game "solver" within the program that checks card layouts throughout a game and calculates the minimal number of moves to complete it. The solver is a "dynamic algorithm that is solving the game at every moment in time, and it knows the minimal number of steps you would need to complete it," Jimison said. "We compare this 'optimal slope' to how the individual users are doing."

"In general, we're trying to keep people at a 75 percent win rate," said Jimison, who also serves as senior research scientist for computer game developer Spry Learning, which received an NIST grant for helping to adapt and test the FreeCell game. "We're trying to keep difficulty at a level that keeps them motivated. We want to challenge them to the point where they just start having trouble. We don't want it to be too easy or too hard."

Right. And according to the boss I have that cognitive impairment part down pat, if not a winning strategy for FreeCell.

Posted by Jon Erickson at 12:00 PM  Permalink |

Back when we launched Dr. Dobb's Handwriting Recognition Contest, the term "biometric recognition" was rarely--if ever--used, and "security" had little to do with handwriting recognition.

These days, biometric recognition and security go, well, hand-in-hand and research into ways to make handwriting recognition more accurate, faster, and secure continues to move forward.

For instance, Juan Jose Igarza Ugaldea of the University of the Basque Country has proposed two approaches to handwritten signature biometric identification--on-line and off-line signature recognition.

At the core of Ugaldea's system is, of course, a database of signatures from anonymous signers and skilled forgerers. (The database is multimodal in that it also includes fingerprints and voices from all users.)

Ugaldea's proposal for on-line signature recognition is based on processing local features (coordinates, velocities, accelerations, pressure, and pen tilt) by using global features (center of mass of ink and principal inertia axes) as a reference system. He then uses a simple scaling algorithm for signature time normalization that is applicable to every local feature. He has limited the amount of local features to feed the Hidden Markov Models (HMM) to nine to balance the required security level and the processing and storing capacities. Using six stated Left-to-Right (LR)-HMM, Ugaldea claims to have obtained error rates equal to those currently considered state of the art.

His proposal for off-line signature recognition consists of two systems based on the LR-HMM technique. The models are fed on spatially ordered point sequences and geometrical "false-dynamic" derivative features. The goal of those proposals is to extend LR-HMMs to the field of static or off-line signature processing using results provided by image connectivity analysis, which separates images in connected components known as "blobs", each one made up of a cluster of adjacent pixels of the same nature.

Ugaldea has proposed two different methods of generating models, depending on how the blobs provided by the connectivity analysis are ordered. In the first proposed method, blobs are ordered according to their perimeter length. In the second proposal, the sorting criterion is based in the natural reading order. The models based on the second criterion are more than adequate for the Latin writing in which signatures have been written.

Your's truly,

Jonathan Erickson

Posted by Jon Erickson at 10:29 AM  Permalink |

I'm not sure what you do to get a "chair" or, for that matter, what you do when you have one. I do know they're generally associated with a university and, more often than not, there's a pile of money involved somewhere, somehow. And that it's an honor to be associated with one.

For instance, Bjarne Stroustrup of C++ fame is a professor of computer science at Texas A&M University and, since 2002, holder of the "College of Engineering Chair in Computer Science." Which means that he teaches several courses and conducts research involving programming tools, techniques, and languages--including the next-generation ISO standard C++0x. Stroustrup has been very productive and gracious in his position, especially when receiving a few months back the Sigma Xi 2005 William Procter Prize for Scientific Achievement which is awarded annually to engineers or scientists who have done important, impressive research, and have communicated the research to counterparts in other fields. In this case, Stroustrup gave his $5000 Grant-in-Aid of Research award to postdoctoral research associate Gabriel Dos Reis who researches theories and practicalities of C++-based software to better fashion. "I think he is very promising and doing brilliant things," Stroustrup said. "He works with me on a project called Pivot, which is to represent and analyze C++ programs, and he is on the ISO (International Organization for Standardization) C++ committee that is developing the next generation of C++."

More recently, the University of Waterloo announced its "Natural Sciences and Engineering Research Council of Canada-Nortel Chair in Advanced Telecommunications Technologies," sponsored by the same. The chair has been established to research 3G and 4G broadband wireless technologies, with Amir Khandani, Professor in Electrical and Computer Engineering at the university, appointed Senior Chair. Khandani also holds a Tier I Canada Research Chair in Wireless Systems.

Other university chairs that come to mind include the Yahoo! Founders Chair at Stanford University, endowed by David Filo and Chih-Yuan "Jerry" Yang, inventors of Yahoo!, which is to be granted to "an individual who has demonstrated entrepreneurial spirit, either through their research activities or through association with a start-up company or other commercial endeavor." Then there's the Watson and Marilyn Alberts Chair in the Search for Extraterrestrial Intelligence the University of California, Berkeley, which was reserved for astronomers involved in the Search for Extraterrestrial Intelligence.

However, the university chair that more recently comes to mind, its sad to say, is the University of Missouri's Kenneth L. Lay Chair in Economics. Alas, although the chair was endowed to the tune of $1.1 million by the now deceased Enron thief, the university can't get anyone to accept the honor.

In the spirit of good chairmanship, the powers that be at Dr. Dobb's have decided to support a chair of their own and I've just as graciously agreed to their kind offer by accepting that chair.

At least I now know that around here a "chair" is in fact a "chair". No strings, no endowments attached.

Posted by Jon Erickson at 10:26 AM  Permalink |

More often than not, every question leads not to an answer, but to another question. For instance, researchers at the University of Manchester are building a computer that mimics the human brain. Great. My question is "who's brain?"

The computer will be the first of its kind and will be used to try and understand how, for example, the details of complex visual scenes are encoded by the brain. It will be designed with the aim of modeling large numbers of neurons in real time and to track patterns of neural spikes as they occur in the brain. The computer will be built using large numbers of simple microprocessors designed to interact like the networks of neurons found in the brain. The aim will be to place dozens of microprocessors on single silicon chip, thereby reducing the cost and power consumption of the computer.

According to Spinnaker project leader Steve Furber, "Our brains keep working despite frequent failures of their component neurons, and this 'fault-tolerant' characteristic is of great interest to engineers who wish to make computers more reliable. Our aim is to use the computer to understand better how the brain works at the level of spike patterns, and to see if biology can help us see how to build computer systems that continue functioning despite component failures."

Sounds fine to me, but my question stands: Who's brain? Might I suggest, say, Larry, Curley, or Moe's instead of, oh, Attila the Hun or Adoph Hitler? That sounds like a no-brainer to me.

Posted by Jon Erickson at 11:53 AM  Permalink |

A guiding light for Dr. Dobb's has always been our belief that computers can indeed make the world a better place--one line of code at a time.

Apparently some folks at Microsoft feel the same way, which is why they've launched the Develop Without Borders Challenge. All you have you have to do is design an application on the 2007 Microsoft Office system between June 26 and August 31, 2006 to help your favorite charity. And if your application is judged to be one of the best, you can your charity win a share of more than $160,000 in awards.

As the Develop Without Borders Challenge web site goes on to say, "as a developer, you have a unique understanding of how technology works. You know how to harness it effectively, to resolve problems and streamline processes. Why not use your talents to help a cause you really care about?"

Application areas that you might want to consider include:

• Fundraising. Charities depend on outside funding, and can spend plenty of time and resources seeking funds. Help them create grant applications faster with an automated process.
• Compliance. The rules and regulations for using donated funds are complex. Use technology to help an organization track data. Create standard forms. Improve workflow approval processes. And keep the charity in good standing with its benefactors.
• Data Management. Many charities monitor an activity as part of their work, be it ecological, educational, or economic. Create a solution that helps them collect, compile and analyze this data.
• Community Outreach. Establishing and maintaining a presence in a community is critical to the success of every charity. Help your organization reach its target audience with wikis, blogs and RSS technology. Streamline the process of creating and distributing newsletters.

Folks, this is a good deal, whether you win a prize or not. Let's all do our part to make the world a better place. Goodness knows it needs all the help it can get.

Posted by Jon Erickson at 11:37 AM  Permalink |

Academically speaking, computer poker is all about game theory. But to the rest of the world, Texas Hold'Em is all about having some fun and making a couple of bucks--or rather, not losing your shirt.

Whether for the excitement, money, or class credits, poker is all the rage these days, even with the American Association for Artificial Intelligence (AAAI) which is holding its first Computer Poker Competition at the upcoming annual AAAI conference.

Among others, entrants include the likes of Carnegie Mellon University and the University of Alberta (my alma mater), both of which have added computer poker to their research. At the U of A, in fact, the Computer Poker Research Group, led by Jonathan Schaeffer (who I interviewed in this podcast) last year, is part of the The University of Alberta GAMES Group which examines game theory across the board, so to speak.

In CMU's case, the poker team is led by computer science professor Tuomas Sandholm and graduate student Andrew Gilpin, who have built a be poker robot called "GS1" developed by Sandholm, who is also director of CMU's Agent-Mediated Electronic Marketplaces Lab, and Gilpin. Though not yet the equal of the best human players, GS1 outperformed the two leading "pokerbots" in playing heads-up, limit Texas Hold'Em in tests at CMU earlier this year. Both of GS1's opponents were commercially available programs that, like other pokerbots, incorporate the expertise of human poker players. GS1, by contrast, develops its strategy after performing an automated analysis of poker rules. Sandholm and Gilpin have since developed an improved version of their game-theory-based program, called "GS2," which will compete in the AAAI event.

Unlike chess, where the status of all of the chess pieces is known to both players, poker forces players to make decisions based on incomplete information. "You don't know what the other guy is holding," Sandholm explained. And the sheer number of possible combinations of cards dealt, cards on the table and bets in two-player Texas Hold'Em games -- 10^18, or a billion times a billion -- makes it impossible for even the fastest computers to fully analyze every hand.

In his computer poker research, Sandholm has developed pokerbots that precompute the strategies for playing the first two rounds of Texas Hold'Em, the so-called "pre-flop" and "flop" rounds, when players are first dealt two cards and then three additional cards are positioned face-up. For the third and fourth betting rounds, the "turn" and the "river," his pokerbots update the probability of each possible hand by taking into account betting as well as the revealed cards. The strategy for those rounds is then computed in real-time for the setting at hand.

To reduce the computational complexity, GS1 and GS2 automatically recognize strategically equivalent hands. For instance, 25,989,600 distinct hands are possible in the second round, but only about a million are strategically different. That's still too many to compute, so the pokerbots group strategically similar hands together. The end result is 2,465 groups, a small enough number to allow computational analysis.

Source code for the contest is available for download. The server for the competition is written in Java and runs on Windows.

Posted by Jon Erickson at 08:47 AM  Permalink |

Being able to get from here to there efficiently is one of the real beneficial features of the Web. And SensorMap, an interface which merges location mapping with real-time data, may take finding your way around to a new level.

SensorMap will leave the world of the lab for the world of commerce when it is released to the public on July 17 at Microsoft Research’s Faculty Summit. In a nutshell, SensorMap is a platform for publishing and searching for real-time data to help users get more tightly focused search results. More specifically, SensorMap is an interface of Microsoft Research's SenseWeb data portal.

"You can go to a search engine and search for all the restaurants in Seattle," says Suman Nath, a researcher at Microsoft Research. "But what you can’t do today is to find me all the restaurants in Seattle that have a waiting time of less than 30 minutes. That part is a real-time component, and we want to enable this type of scenario, so that you can search based not just on static data, but also on real-time data."

From the SensorMap perspective, there are two types of data--live data, which changes over time, and metadata that describes the sensor itself and which doesn’t change that much. SensorMap doesn't really care what the source of the data is. For instance, "sensors" might be wireless transmitters placed at various remote sites that broadcast information relevant to the location. The wireless transmitters send local information--such as a restaurant’s table availability or the temperature at a national forest during fire season--to a Web server. To enable this, Microsoft provides the MSR Networked Embedded Sensing Toolkit (MSR Sense), a collection of software tools that allow users to collect, process, archive, and visualize data from a sensor network. The current version contains:

• A reconfigurable microserver execution environment (mSEE)
• A small library implementing signal processing and event detection algorithms
• An extension to Excel 2003 (Senscel) to import, visualize and processing sensor data, and interface to SQL server to archive and retrieve data
• A microserver interaction console (mSIC) for users to configure and control microservers.

Once live real-time data is collected, SensorMap indexes it to make it searchable. A database holds geographically indexed sensor descriptions and works in tandem with a sensor-data publishing Web service and a server-side query processor.

"In our system, we have one central database where we store all the metadata," says Nath. "When you make a query, the query first goes to that central database, and it returns a list of sensors relevant to the query. Another module talks to those sensors directly, gets the live data, processes that data, and sends it back to the user."

Nath goes on to say that "the biggest problem is the query-processing part. And the biggest challenge in this whole space is scalability. If you have thousands of sensors and if you have many, many users, how can we scale efficiently to that? How can we cache data on the back end so we can reuse that data for scaling?"

"What we are trying to do here, " he adds, "is to bring all different types of sensors together. And we’re actually trying to provide more useful things--search based on geographic region or based on keywords. Also, depending on the zoom level of a map, we are trying to aggregate data. If you’re querying temperature sensors statewide, we can provide individual sensor information, but we also can show you the average temperature. That sort of aggregation is absent in other industry applications."

Posted by Jon Erickson at 09:59 AM  Permalink |

Registration is underway for the 9th annual ICFP Programming Contest.

Hosted by Carnegie Mellon University's Principles of Programming (POP) Group, the contest is associated with the upcoming International Conference on Functional Programming, a forum for programmers to learn about recent work on the design, implementations, principles, and uses of functional programming.

Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. Functional programming languages, which have their roots in Lisp and APL, includes the likes of Erlang, Haskell, Dylan, and Mondrian , to name a few. The functional paradigm can also be implemented in more mainstream languages, such as Java.

The contest will run from July 21-24, 2006, with the contest challenge announced at 12:00 (noon) EDT on July 21, and entries acccempted until 12:00 (noon) EDT on July 24. A few days prior to the start of the contest, contest organizers will make some required materials available on the contest web site. (The International Conference on Functional Programming Conference itself takes place September 18-20, 2006.)

There is no entry fee or need to pre-register and everyone, except for CMU faculty, students, and staff, is eligible. Teams may work from any location. For ICFP 2006, there are two divisions: small teams and large teams. A small team consists of 0–4 persons. A large team may have any number of members. Teams may switch from the small team division to the large team division at any time (even once the contest has begun) if they wish to take on new members. Large teams are not eligible for the first prize, but otherwise the two divisions are identical. Teams may work in any programming language(s) that they wish, and use any computational resources at their disposal.

Now for the good stuff: There will be four prizes: First, second, and third place, as well as a discretionary judges' prize. Prize money totaling $1750 will be awarded to help defray the costs of travel to the contest for the winners and for small cash prizes.

Posted by Jon Erickson at 08:59 AM  Permalink |

Vulnerable. A scary word these days. Just hearing it puts to mind a bunker mentality, whether it be traveling, standing in line for coffee, or using software. Yes, even software is vulnerable to attack.

In fact, between 1995 and 2006 (Q1), the CERT reported 24,313 vulnerabilities--defects in software that can let attackers bypass security measures. In 2005 alone, 5198 newly discovered vulnerabilities were reported by CERT.

Robert Seacord, a senior vulnerability analyst at the CERT and author of Secure Coding in C and C++, has written widely about software vulnerabilities in Dr. Dobb's; see, for instance, "Wide-Character Format String Vulnerabilities" and "Validating C and C++ for Safety and Security".

Recently, Yashwant K. Malaiya, professor in the Colorado State University Department of Computer Science, and Omar Alhazmi, a doctoral student, have developed a model to predict with much greater accuracy the number and severity of vulnerabilities that will likely surface in operating systems and in major software applications in the near future.

"The hope is that a vulnerability gets patched before it gets exploited," Malaiya said. "Each individual vulnerability discovered can be widely reported to the public, and in some cases, it has caused the value of the stock of the company to drop."

It is impossible to implement an operating system like Windows XP or Linux, Web servers like Apache or Microsoft IIS, or Web browsers that are free from vulnerabilities, Malaiya said. If developers knew when and how many patches will be needed in a certain period of time, they could be better prepared to quickly develop patches and ensure the security of such applications and systems, he said.

Malaiya's group has developed two complementary approaches to predict vulnerabilities--modeling of the vulnerability detection rate with the Alhazmi-Malaiya Logistic model and based on the developer, predicting the number of vulnerabilities per 1000 lines of code.

Applications of such data can be far-ranging, Malaiya said. Companies like Microsoft can project the manpower needed to quickly develop and release patches to minimize the probability of exploitation. An investment company, such as a bank or a brokerage, can better assess the potential risk levels because products containing more projected vulnerabilities tend to be riskier products.

The Alhazmi-Malaiya Logistic model has already seen success in its predictions:

• In 2005, it predicted the number of vulnerabilities discovered in Windows XP would grow rapidly. It has indeed grown from 88 in January 2005 to 173 by the latest count, making the vulnerability density of XP comparable to that of earlier version of Windows.

• The model predicted that very few new vulnerabilities will be found in Red Hat Linux 6.2, and the number has stayed unchanged at 117.

• It predicted that the number of vulnerabilities of Windows 2000 will eventually range from 294 to 410. At that time of the prediction, the number was 172; it now is 250, and vulnerabilities are still being found.

Posted by Jon Erickson at 11:28 AM  Permalink |