Advertisement

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.
Research and Advances

Cyc: toward programs with common sense

Cyc is a bold attempt to assemble a massive knowledge base (on the order of 108 axioms) spanning human consensus knowledge. This article examines the need for such an undertaking and reviews the authos' efforts over the past five years to begin its construction. The methodology and history of the project are briefly discussed, followed by a more developed treatment of the current state of the representation language used (epistemological level), techniques for efficient inferencing and default reasoning (heuristic level), and the content and organization of the knowledge base.
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

Building bilingual microcomputer systems

In the Arab world the need for bilingual microcomputer systems is ever increasing. In addition to the ability to process the Arabic and English scripts, an ideal system should support the use of existing applications with Arabic data and the access to the system facilities through Arabic interfaces. The Integrated Arabic System (IAS) was developed to study the feasibility of building such systems using existing microcomputers and software solutions.
Practice

Six-digit coding method

The Six-Digit Coding Method (SDCM) is a new coding method for Chinese characters. It is based on the structural analysis of Chinese characters. We recently developed this method and have successfully used it to code 11,100 characters, including the simplified, traditional, and variant forms found in Xin Hua Dictionary [7]. This article illustrates the basic principes, features, and some viewpoints concerning the method.
Practice

Automatically generating visual syntax-directed editors

Since inexpensive computers possessing sophisticated graphics were introduced in the late 1970s, program development research has focused on syntax-directed editors that are based on the grammars of their underlying languages. The system presented here automatically generates object-oriented, syntax-directed editors for visual languages, which are described by a family of editing operations.
Research and Advances

Dynamic file migration in distributed computer systems

The importance of file migration is increasing because of its potential to improve the performance of distributed office, manufacturing and hospital information systems. To encourage research in the file migration problem, the authors summarize accomplishments of researchers of the problem, provide a detailed comparison of file migration and dynamic file allocation problems, and identify important areas of research to support the development of effective file migration policies.
Research and Advances

Investigating the effects of color

A laboratory experiment studies the effects of color on a decision maker's ability to extract information from different graphical and tabular presentations. Results indicate color improves time performance for tables, pie charts and bar graphs, and accuracy performance for pie charts and line graphs.
Research and Advances

Smart game board and go explorer: a study in software and knowledge engineering

Software engineering is an established discipline that has accumulated and codified more than two decades worth of know-how. Knowledge engineering, on the other hand, is an emerging discipline with lots of issues but, at least so far, little structure. Despite its lack of maturity the practice of knowledge engineering promises to have a noticeable impact on software engineering doctrine. The experimental nature of knowledge engineering goes hand-in-hand with a style of software development best characterized as ‘exploratory,’ which has not been much studied in traditional software engineering.

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