Search
Join ACM

Computing Profession

Advertisement

Opinion

Computer perspectives: the bandwidth famine

A number of years ago I visited a young and successful computer company and was given a tour of the facilities by one of the directors. We passed offices in which people were working at computer terminals; I was told they constituted the accounts department. A little further on we came to the software department; here people were also using terminals. “Now,” said my host, “I will show you the hardware department.” To my surprise, instead of the oscilloscopes and waveform analyzers that I had expected to find, I saw more computer terminals. This was a sign of the times.Today, the designer of printed circuit boards such as those intended to be plugged into PCs, has a great variety of software tools from which to choose: programs for layout and routing; programs for checking that the design rules have been followed correctly; logic simulators for checking that the design is functionally correct; and more elaborate simulators for checking the timing. These tools make it possible to produce a working prototype without performing any experimental work on a laboratory bench.In the dark ages of electronics, the debugging of circuits was carried out using experimental versions made by screwing the components down on a piece of wood and connecting them. The behavior of the circuit was checked using an oscilloscope. These experimental versions were known as breadboards, because someone had compared them to those boards on which bread was sliced. The wooden board has been obsolete for years, but the term has survived. A modern version of the breadboard (still used occasionally) is the wire-wrapped prototype. It is, however, costly in time and money and the effort spent on it does not advance the physical design of the final product. Moreover, in certain respects, particularly as regards electrical interference and cross talk, the wire-wrapped version may give misleading information.
Practice

Physical design equivalencies in database conversion

As relational technology becomes increasingly accepted in commercial data processing, conversion of some of the huge number of existing navigational databases to relational databases is inevitable. It is thus important to understand how to recognize physical design modifications and enhancements in the navigational databases and how to convert them to equivalent relational terms as applicable.
Research and Advances

A bridging model for parallel computation

The success of the von Neumann model of sequential computation is attributable to the fact that it is an efficient bridge between software and hardware: high-level languages can be efficiently compiled on to this model; yet it can be effeciently implemented in hardware. The author argues that an analogous bridge between software and hardware in required for parallel computation if that is to become as widely used. This article introduces the bulk-synchronous parallel (BSP) model as a candidate for this role, and gives results quantifying its efficiency both in implementing high-level language features and algorithms, as well as in being implemented in hardware.
Opinion

Legally speaking: should program algorithms be patented

In the Legally Speaking column last May [6], we reported on a survey conducted at last year's ACM-sponsored Conference on Computer-Human Interaction in Austin, Tex. Among the issues about which the survey inquired was whether the respondents thought patent protection should be available for various aspects of computer programs. The 667 respondents overwhelmingly supported copyright protection for source and object code although they strongly opposed copyright or patent protection for “look and feel” and most other aspects of programs. Algorithms were the only aspect of programs for which there was more than a small minority of support for patent protection. Nevertheless, more than half of the respondents I opposed either copyright or patent protection for algorithms. However, nearly 40 percent of the respondents regarded algorithms as appropriately protected by patents. (Another eight percent would have copyright law protect them.)We should not be surprised that these survey findings reflect division within the technical community about patents as a form of protection for this important kind of computer program innovation. A number of prominent computer professionals who have written or spoken about patent protection for algorithms or other innovative aspects of programs have either opposed or expressed reservations about this form of protection for software [2, 4, 5].This division of opinion, of course, has not stopped many firms and some individuals from seeking patent protection for algorithms or other software innovations [8]. Although the Refac Technology patent infringement lawsuit against Lotus and other spreadsheet producers may be in some jeopardy, it and other software patent lawsuits have increased awareness of the new availability of software patents. This situation, in turn, has generated some heated discussion over whether this form of legal protection will be in the industry's (and society's) long-term best interests.The aim of this column is to acquaint readers with the legal debate on patent protection for algorithms and other computer program innovations, an issue which seems to be as divisive among lawyers as those in the computer field. [3, 9].
Practice

Agenda: a personal information manager

The free-form, evolving, personal information that people deal with in the course of their daily activities requires more flexible data structures and data management systems than tabular data structures provide. A tool for managing personal information must conveniently handle freetextual data; allow for structure to evolve gracefully as the database grows; represent unnormalized data; and support data entry through database views. We have designed a new type of database that serves these needs—“item/category” database—and realized this design in a commercial personal computer software product named “Agenda.”
Opinion

Personal computing: simple complexity and COMDEX

One of today's emerging paradigms is the view that complex behavior or form can emerge from the interaction of relatively simple components, if you have enough of them and they have enough time to do whatever they do. The emergent behavior or form might seem systematic or chaotic. Some examples are neural nets, cellular automata, fractals, electronic mail networks, market economies, whirlpools, and snowflakes. Years ago, similar systems were often called self-organizing, and they were found in models of memory, pattern recognition, multilevel stores, and libraries. The area languished, however, awaiting the development of theory and powerful hardware. Personal workstations played an important role in facilitating experimentation and mass market personal computers are now up to the task.
Research and Advances

The politics of standards and the EC

European legislation and power struggles in the standards arena are sparking fear of technical barriers to trade and prompting the American standards community to reevaluate its infrastructure. The National Institute of Standards and Technology may step up its role in order to negotiate at a governmental level with the EC.
Research and Advances

Constraint logic programming languages

Constraint Logic Programming (CLP) is an extension of Logic Programming aimed at replacing the pattern matching mechanism of unification, as used in Prolog, by a more general operation called constraint satisfaction. This aritcle provides a panoramic view of the recent work done in designing and implementing CLP languages. It also presents a summary of their theoretical foundations, discusses implementation issues, compares the major CLP languages, and suggests directions for further work.
Opinion

From Washington: budget FY 1991: the numbers tell the R&D story

This is the time of year when talk turns to fiscal budgets. In Washington, however, such banter typically involves astronomical sums of money.When President Bush released his proposed budget for FY 1991 last January, the reaction from the scientific community was mixed. Many observed that seldom have research and development (R&D) projects been given as prominent a place in a federal budget. Other industry watchers, while less enthusiastic, had to agree that in many respects R&D fared better under this year's budget than last year's.However, understanding the details of the budget is far more important than reviewing its broad outlines. For that reason, the American Association for the Advancement of Science (AAAS) calls members of the scientific community to Washington each spring to dissect, denounce and defend the government's R&D funding plans for the next fiscal year.The Colloquium on Science and Technology Policy conference centered around the analytical findings of the AAAS's Research and Development FY 1991 report. The three-day conference was peppered with high-ranking White House officials who either defined the specific branches of the government's R&D interests or discussed the possible implications the budget poses for future projects.There is an overall 7 percent budget increase for R&D, with a 12 percent increase in nondefense R&D programs and an 8 percent increase in basic research. In the area of computer science and engineering, DARPA, NSF, and the ONR remain the largest sources of government funds for R&D.Federal support in computer science is divided into two basic categories: defense and civilian. More than 60 percent of total federal R&D expenditures in computer science and engineering are supported by the defense sector. Moreover, federal R&D activities are conducted in government and nonuniversity labs as well as in universities. The majority of the funding for computer science research supports activities outside of universities.D. Allan Bromley, director of the Office of Science and Technology Policy (OSTP), explains the thinking behind the President's budget: To prioritize funding requests, the Office of Management and Budget follows three basic guidelines. They include 1. Programs that address national needs and national security concerns, 2. Basic research projects, particularly university-based, individual and small group research, and 3. Adequate funding for the nation's scientific infrastructure and facilities. Bromley points out that one of the primary avenues OSTP will emphasize this year is high-performance computing—a dynamic technology for industrial, research and national security applications. Of first concern will be the development of hardware to enhance mainframes and address the parallelism needed to make TERAOP computers perform trillions of operations per second. The next phase will be software development, followed by the construction of a fiber optic network.Bromley, who also serves as assistant to the President for Science and Technology, calls the FY 1991 budget an excellent one for R&D. However, he is quick to add there are problems with those numbers. (One of the most serious involves the funding rate for grants at the NSF and National Institute of Health (NIH). Despite a decade of funding increases, the money available for new, young investigators is very tight. Indeed, the scientist community is partly to blame, he says.“We argued for multiyear grants and contracts to cut down on the amount of paperwork required to do research,” recalls the OSTP director. “Both NSF and NIH have responded to those requests, and in the process they built substantial ‘outyear mortgages&rsquo’ for themselves.”
Research and Advances

The 20th annual ACM North American computer chess championship

Despite entering ranked almost a class above the field, a last-round loss forced DEEP THOUGHT to settle for a first-place tie with HITECH at the 20th Annual ACM North American Computer Chess Championship. The five-round Swiss-style tournament was held November 12-15 at Bally's-Reno in conjunction with Supercomputing '89. It marked the twentieth consecutive year that ACM has organized this major chess event. Until 1988, the tournament took place at the Annual ACM Conferences. In 1988 and again this year, however, the event was hosted by the joint ACM SIGARCH/IEEE Computer Society Supercomputing Conference. Ten teams participated in the strongest computer chess tournament in history. Every program was playing at least at the Expert level. This year's tournament offered $5000 in prizes. HITECH and DEEP THOUGHT's programmers each won $2000 for their first-place tie while MEPHISTO X and BEBE's programmers split the $1000 third-place prize. In addition to the cash prizes, trophies were awarded to the first three finishers. A special trophy was given to MEPHISTO X as the “Best Small Computing System.” A Technical Session chaired by Tony Marsland was held during the championship. The topic of the session was endgame play by computers. Once upon a time computers played the endgame particularly badly, but this is no longer the case. The session considered some of the improvements and some of the problems that remain. David Levy served as Tournament Director, returning after a layoff of almost a decade. He served as TD for the first time in 1971, continuing into the early 1980s when his own programs began to compete. Levy will take on DEEP THOUGHT in London in a four-game match in December.* In 1978, he won a bet made in 1968 that no computer would defeat him during the following ten years. This time he appears to be the underdog. Attending the championship as an Honored Guest was Ben Mittman. Mittman was head of Northwestern University's Vogelback Computing Center during the years that Slate, Atkin, and Gorlen's programs dominated the ACM events. Some give him credit for being Northwestern University's greatest and most successful “coach.” From 1971 through 1983, Ben also was involved in the organization of the tournaments, From 1977 through 1983, Ben served as the first president of the International Computer Chess Association. He was also the first editor of what is now called the ICCA Journal, the main journal for technical papers on computer chess. This year the championship is scheduled to be a part of Supercomputing '90 in New York City on November 11-14. The 1990 event will see the first major change in the tournament rules. For the last 20 years, the rules have specified that each player is given two hours to make the first 40 moves and an additional hour for each 20 moves thereafter. Games frequently lasted more than six hours. This year, each computer will be required to make all its moves in two hours, thus guaranteeing that no game will last more than four hours. In addition to the main championship, a special endgame tournament will be held testing the programs' abilities in this special part of the game. For the first time at Supercomputing '90, all games will be played during the day beginning at 1:OO p.m.—except for one 7:00 p.m. Sunday evening game on the 11th. The event will be a five-round Swiss-style tournament. For information contact Professor Monty Newborn, School of Computer Science, McGill University, 3480 University Street, Montreal, Quebec, Canada, H3A. 2A7.
Practice

Concurrent operations on extendible hashing and its performance

Extendible hashing is a dynamic data structure which accommodates expansion and contraction of any stored data efficiently. In this article, an algorithm has been developed for managing concurrent operations on extendible hashing by achieving optimal memory utilization by supporting directly expansion and contraction, page split, and merge. The results of this study have been encouraging in the sense that it seems to provide a higher degree of concurrency compared to other algorithms on an extendible hash file.
Practice

Typographic style is more than cosmetic

There is disagreement about the role and importance of typographic style (source code formatting and commenting) in program comprehension. Results from experiments and opinions in programming style books are mixed. This article presents principles of typographic style consistent and compatible with the results of program comprehension studies. Four experiments demonstrate that the typographic style principles embodied in the book format significantly aid program comprehension and reduce maintenance effort. —Authors' Abstract
and

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More