Dr. Dobb's Journal November 2000
A team of computer scientists claims to have solved a 32-year-old mathematics problem known as the "quadratic assignment problem." The problem (also called "NUG30") was first proposed in 1968 as a test of computer capabilities. The combinatorial optimization problem involves determining the most efficient assignment of 30 facilities to 30 locations to minimize the total cost of transferring materials between the facilities.
Using 1000 computers in 13 locations running for a week, researchers from Argonne National Laboratory, the University of Iowa, and Northwestern University, finally solved the problem. The key to the solution was an algorithm developed by Kurt Anstreicher and Nate Brixius of Iowa. Jean-Pierre Goux of Northwestern and Argonne, and Jeff Linderoth of Argonne, along with Sanjeev Kulkarni and Mike Yoder of the University of Wisconsin at Madison, spearheaded the design of a "Master-Worker distributed processing interface," which was used to execute the algorithm on the Condor distributed computing system. Condor (part of the metaNEOS project running at several universities) uses the idle time on PCs and user workstations to perform computations. (For more information, see "The Condor Distributed Processing System," by Todd Tannenbaum and Michael Litzkow, DDJ, February 1995.) At its peak, the algorithm was simultaneously running on 1000 computers, solving close to 1 million calculations per second. According to Steve Wright of Argonne, "This was one of the largest and most complex computations ever performed to solve a discrete optimization problem." For more details, refer to http:// www.mcs.anl.gov/metaneos/nug30/.
The World Wide Web Consortium has issued a Scalable Vector Graphics (SVG) specification as a "W3C Candidate Recommendation," inviting web developers to "make implementations of SVG and provide technical feedback." SVG provides methods for incorporating vector graphics into XML documents. According to a W3C press release, SVG "enables the textual content of graphics -- from logos to diagrams -- to be searched, indexed, and displayed in multiple languages. Related W3C specifications such as the Document Object Model (DOM) allow for easy server-side generation and dynamic client-side modification of graphics and text." The SVG Working Group consists of the major graphics companies such as Adobe, Canon, and Xerox, as well as major computer vendors such as HP, IBM, Sun, and Apple. For more information, see http://www.w3.org/ Graphics/SVG/Overview.htm8.
Intel has announced a chip microarchitecture designed for a variety of wireless applications. Based on the StrongARM technology acquired by Intel, the so-called XScale microarchitecture offers low-power operation ranging from 1/10,000 of a watt to 1.6 watts, with clock speeds approaching 1 GHz. The XScale core includes extensions from the ARM architecture such as ARM Thumb instructions to reduce code size and ARM media extensions to add digital signal processing capabilities. Intel claims that major embedded operating systems such as Windows CE, VXWorks, IxWorks, EPOC, and Embedded Linux will support XScale.
While red BSD horns and clever T-shirts mocking Microsoft were all the rage at LinuxWorld Expo, Windows wasn't the only object of derision. In his conference keynote presentation, Michael Dell, chairman and CEO of Dell Computer, asserted that Linux "makes far more economic sense than the proprietary model." He praised the low cost, speed of development, flexibility, stability, and level of support of Linux, and predicted unflagging growth for Linux over the next few years. Dell even went so far as to suggest that Linux might become the UNIX Standard. "UNIX has really consolidated around Solaris and Linux," he said, "and we don't think Solaris is the answer." In an attempt to challenge Dell's claim that "we don't think Sun is going to support Linux," Sun actively promoted OpenOffice and the availability of Java 2 on Linux.
Still, the biggest news from the conference was the launch of the new GNOME Foundation (http://www.gnome .org/pr-foundation.html), a group of developers and corporate interests dedicated to establishing GNOME as a unified user environment across UNIX and Linux platforms. The foundation will be modeled on the Apache Foundation, with a board of directors elected by the project developers.
Questions were immediately raised about the status of KDE (http://www.kde.org/) in light of the new effort to standardize GNOME as the UNIX/Linux user environment. "We have no intention of dropping KDE. It becomes up to the customer to choose which technology best suits their need," said Red Hat's Bob Young. "Competition is a good thing...GNOME is much better as a result of the existence of the KDE project." But HP, for one, did acknowledge that GNOME will be the "default desktop" of HPUX in the future.
For the robotics industry, the interoperability enabled by open architectures is critical to reducing the price of integrating disparate robotics systems. According to the National Institute of Standards and Testing (NIST), the lack of open standards annually costs the U.S. industry from $2 billion to $4 billion when integrating robots into manufacturing systems.
NIST and the Robotics Industries Association are now working together to address the issue of open architecture controls for robotics. In February 2000, participants from the three key sectors of the robotics market -- system integrators, vendors, and end users -- formed a working group to examine current open architecture control standards (such as those for machine tools) from the perspective of robotics, established guidelines for data integration in factory networks, and created a web site with a glossary, references, and links (http://www.isd.mel.nist.gov/ projects/openarch/).
In June 2000, the group refined its definition of open architecture controls with two new concepts. The first split robot controllers into a proprietary part and an open (typically PC-based) part. The second identified three classes of external interfaces to the open part of a robot controller that would be proper areas for standardization: factory data integration, peripheral integration, and graphical display. Group members agreed to focus initially on factory data integration, proposing "first-wave standards" for media and protocols, information presentation, time synchronization, and network management. In an upcoming November 2000 meeting, the working group will begin developing case studies and proposals.