CS201 Summary #1 Leslie Valiant, Harvard University Cognitive Computation UCLA CSD Distinguished Lecture 3/20/97 This Distinguished Lecture was presented by Leslie Valiant, well known for a number of fundamental contributions in theoretical computer science including the BSP model of parallel computation and PAC learning theory. In this talk, Valiant presented a synthesis of his recent work on the foundations of an approach to artificial intelligence that he calls "cognitive compuation". This approach is characterized by an emphasis on learning (in particular, inductive learning), and an architecture that (at least at a very superficial level) is compatible with neural architecture. Valiant's architecture is composed of a network of circuit units and image units. Circuit units are perceptron-like linear threshold units which employ a PAC-learning algorithm (which has desirable theoretical properties such as polynomial complexity and bounded number of training instances). Image units are black-boxes that, like circuit units, take propositional vectors as input and output propositional formula. Valiant intends for circuit units to handle the routine, reflexive behavior, while image units handle knowledge-intensive, complex behaviors (i.e., anything that can't be handled by circuit units). Putting this work in to perspective, it is clear that a major motivation of this work is to push PAC-learning theory, which has always been the domain of a relatively isolated group of computational learning theorists, into the mainstream of AI. While the importance of incorporating inductive learning in a cognitive architecture is certainly obvious, It is not clear that Valiant's cognitive architecture presents a significant contribution. The major problem is that all of the complexity and the problems that arise in non-toy domains is swept under the rug and is "handled by the image units". No significant evidence is given (either in this talk, or in Valiants recent extended abstract "Rationality", a Harvard Division of Applied Sciences Tech Report) that this architecture is scalable, and has some practical utility. The only empirical results are with toy/synthetic domains such as Blocks World. In summary, although Valiant tries to construct a cognitive architecture focused on PAC-learning, much more is needed in order to convince the AI community that this is a viable approach to building useful systems. ----------------------------------- CS201 Summary #2 Andrew A. Chien, University of Illinois, Urbana-Champagne High-performance Virtual Machines UCLA CSD Faculty Candidate Talk, 2/18/97 The goal of the High Performance Virtual Machines (HPVM) project is to use commodity hardware and software components to build a reliable, high-performance distributed system. The project targets emerging applications such as scalable web servers, data mining, and interactive data visualization, as well as traditional high-performance computing applications. The approaches being studied in the HPVM project include: (1) Improvement of cluster performance using resource scheduling that is external to the operating system (the Concert system), (2) Multimedia support in both lightweight and traditional protocols, and (3) Fast Messages (FM), an efficient implementation of a lightweight protocol which bypass the OS to provide high bandwidth and low-latency, whose implementation on Solaris/Myrinet achieves both 140Mbps throughput and 11 microsecond latencies for short messages The goal of the FM messaging layer is to provide the network's hardware performance to the application level for small messages. According to Chien, providing bandwidth for large messages is relatively easy. However, spooling time for messages can hide a significant amount of overhead. Providing low latency and high bandwidth for small messages is a significant performance challenge. The FM messaging layer is a simple set of primitives for low-level programming. FM has been implemented on Sun Sparcstations and Myrinet. The Illinois Concert System is a concurrent object-oriented language that focuses on interprocess communication and an efficient runtime system that attempts to exploit fine-grained parallelism (~100 instructions). Concert has performed well on implementations of a number of application kernels, and provides fast (3 microsecond) remote procedure calls. ----------------------------------- CS201 Summary #3 Keith Golden, University of Washington, Seattle Planning for the UNIX Softbot The Unix Softbot project at the University of Washington has gotten a significant amount of popular press coverage in the past few years (e.g., top 10 technical innovations award in Discovery magazine). The project was one of several projects that pioneered the concept of software agents based which applied AI technology in interactions with real software environments such as Unix and the Internet. Implementing a planner to handle routine tasks in a Unix environment required the development of new planning techniques that handled the problem of incomplete information. Specifically, a tractable formalism for representing partial knowledge about the state of the world is required. Classical planners apply the closed world assumption (CWA), which asserts that anything not known to be true is assumed to be false. An alternative is the open world assumption (OWA), which applies a three-valued logic to assert that anything not known to be either true or false is unknown. The CWA is tractable, but is limited in expressivity. The OWA is expressive, but intractable. Golden's major contribution is, Local Closed World (LCW), which asserts that a particular predicate is known for all variables. Golden shows that propagation and revision of LCW can be done in polynomial time, and presented the XII planner, a sound and complete planner based on LCW. The greatest weakness of this work is the "single-agent assumption", i.e., the planning agent is the only cause of change int he world. Clearly, this assumption is invalid in a multi-user Unix environment (or any networked environment). The presence of other agents can render all of the agent's knowledge invalid (since another agent can change arbitrary state values). It may be possible to work around this by "aging" the agent's knowledge base; however, experimental work is necessary to show the effectiveness of this workaround. ----------------------------------- CS201 Summary #4 Networks of PCs as High-Perormance Servers: The Shrimp Approach Kai Li, Princeton University CS201 2/19/97 The availability of high-performance commodity hardware is enabling the development of high-performance distributed systems based on commodity hardware. SHRIMP (Scalable, High-Performance, Really Inexpensive Multi-Processor) is a parallel machine being designed and built in the Computer Science Department at Princeton University. Shrimp is built from commodity parts. SHRIMP uses Pentium PCs as its computing nodes, and the routing network is the same one used in the Intel Paragon. Li's group is building a network interface card that connects the PCs to the routing network, and are creating the systems software (built on top of Linux/OSF) to make SHRIMP a fully usable multicomputer. SHRIMP uses an innovative model of communication called "virtual memory mapped communication". This has several advantages over existing systems: it allows communication directly from user-level without violating protection, it enables very-low-overhead implementations of message-passing, and it is only a little bit harder to design and build than conventional DMA-based interfaces. SHRIMP is also being used as a testbed for a distributed frame buffer to support multi-computer rendering. ----------------------------------- CS201 Summary #5 The Art and Science of Cause and Effect Judea Pearl, UCLA UCLA Faculty Research Lecture 10/29/96 In this Faculty Research Lecture, Pearl reviews his recent work on causality, which is a natural extension of his work on the Bayesian network formalism for probabilistic reasoning. In ancient times, causality was ascribed to gods and other supernatural agents. Galileo precipitated a scientific revolution that emphasized the "how" over the "why" - description can be explained using mathematics. This had the profound effect of deemphasizing causality. Hume argued further that the "why" is superfluous to the "what/how". Subsequently, causality was virtually purged from the sciences (esp. physics). Statisticians in the early 20th century, epitomized by the work of Pearson, denied the need for the notion of causation, beyond simple correlation. Pearl argues for a revival of the study of causality, motivated in part by the utility of causation as a attention-focusing mechanism in artificial intelligence (the robot planning problem -- what changes in the world does an action cause?). However, an intuitive, consistent implementation of causality in robot programs forces a closer look at the representation of causality. Pearl proposes a representation of causal relationships using equations annoted with graphical structures (a la Bayesian networks). The highlights of this approach are: (1) the treatment of causation as a summary of behavior under interventions, (2), the use of equations and graphs as a mathematical language within which causal thoughts can be represented and manipulated, and (3) the treatment of interventions a s a surgery over equations. In this framework, an intervention (action) is the deletion of equations involving the variable which is fixed (by intervention). Pearl further proposes a calculus for manipulations involving actions and observations. To date, this framework has been applied to problems in policy analysis. ----------------------------------- CS201 Summary #6 Java Chips Marc Tremblay Sun Microsystems Inc. UCLA CSD Research Review Java is a object-oriented, architecturally neutral, language that has received much public attention in the past year or so. This talk presented an overview of Java, followed by some details on Sun's recently announced Java chips. According to Tremblay, there are already half as many "serious Java programmers" as Windows programmers, and the number is growing. This is due to Java's network-centered, object-oriented, multi-threaded, architecture-neutral features, which enables scaleable applications on all segments of computing, including servers, desktops, and embedded systems. In the Java architecture, Java code is compiled into class files which contain bytecodes. Currently, bytecodes are executed on CPUs through an interpreter (slow) or just-in-time compilers. Sun is developing a hardware architecture which is optimized to support Java. This includes the picoJava (for the embedded market), microJava (for network computers), and UltraJava (for high-end multimedia). picoJava is particularly well-suited for embedded systems because of the Java bytecodes are space efficient (2x smaller than RISC code from a C++ compiler). This compactness is due to the fact that Java is a stack-based architecture; there are no register specifiers in the instructions, and all local variables are accessed relative to a base pointer. Early testing of the Java chip revealed that the instruction distribution for a set of benchmarks contained a large number of loads. Instruction folding was abelt to hide up to 60% of the loads, resulting in an instruction distribution similar to that of RISC processors. Lessons learned from RISC chip implementations (e.g., pipelining, implementing only critical instructions in hardware) were applied to the Java chip whenever possible. Support for thread synchronization and garbage collection was also built into the Java chip. Comparison of the picoJava chip with Intel architectures running Java show that the picoJava is about 11 times faster than the Pentium running a Java interpreter, and 5 times faster than the Pentium running a just-in-time compiler. ----------------------------------- CS201 Summary #7 Medical Imaging and Information Systems Wesley Chu, Alfonso Cardenas, Ricky Taira KMeD is a knowledge-based multimedia medical database system developed at UCLA which has been applied to radiological databases. Medical queries are difficult because they involve multimedia, and are temporal, spatial, and imprecise. KMed implements solutions to each of these problems. Traditional object constructs are the "is-a" and "part-of" relations. KMed's temporal evolutionary data model augments this with evolutionary constructs (evolution, fusion, fission) and temporal constructs (super/subtypes and peer types). KMed allows image retrieval by content. Features such as size, texture, shape, and density can be used in queries, as well as spatial relations such as angle of coverage, contact ratio, and relative direction. Evolution of object growth (fusion,fission) can also be used. Query relaxation and association techniques are supported by KMed. Relaxation consists of generalization and specialization via conceptual queries (supported by a type abstraction hierarchy, which privides a multi-level knowledge representation). Thus, KMed supports cooperative querying, in which relaxation and association techniques are applied to user queries to provide more informative responses than would be given by a simple interpretation of the original query. Models of the users are maintained to enable customized query processing. KMed supports visual querying, in which a GUI is used to specify queries involving spatial relationships between objects. Finally, KMed has a timeline interface, which enables users to interact with temporal, multimedia data. ----------------------------------- CS201 Summary #8 Progress in Nomadic Computing Leonard Kleinrock and Jerry Popek UCLA CSD research review Nomadic computing seeks to support computing/communications capabilities required for mobile computing in a transparent, integrated and convenient form. The challenges of nomadic computing arises from the following observation: current systems treat radically changed connectivity or latency as exceptional cases, but in nomadic computing, such cases must be treated as the norm. Current systems depend on location, networking devices, computing platforms, and reconfiguration is difficult. In nomadic computing, seamless switching among various communications devices is a necessity. Transparency with respect to location is necessary - it is not acceptableto have to reconfigure the system every time the user moves to a new location. Communications speed is also a major problem. Dealing with low bandwidth, high latency, high error rate wireless links is very difficult, particularly when they are mixed with high-speed low-latency, low-error rate wired links. Running distributed applications when connectivity is intermittent poses a serious problem (client/server relations are meaningless when the server is unreachable). Providing security is difficult. The ultimate goal of nomadic computing is to hide all of these complexities from the user, so that the user always has the illusion of connectivity, and will not suffer reduced service as he travels nomadically. At UCLA work on nomadic computing seeks to develop and integrate a number of components including the Ficus/Truffles/Rumor File system and the Seer predictive cachine mechanism, with the standard Windows95 and Linux environments. Performance models and mathematical analysis of the nomadic environment is required. This Travler architecture also incorporates adaptive agents to handle unpredictable performance, by using prefetching techniques. The talk concluded by noting that relatively little work had been done in the area of nomadic computing ----------------------------------- CS201 Summary #9 Generalized Hash Functions Robert Uzgalis, Univ. Auckland CS201, 5/24/97 A generalized hash function should uniformly distribute any input set. The common theoretical view on this is that in the worst case, this is impossible, and that the statistical distribution of the input is always reflected in the output distribution. Thus, hashing has traditionally been dismissed as a hack without useful theoretical guarantees. Carter and Wegman introduced Universal Hash Functions, which uniformly distribute an entire domain of inputs (but not the outputs). The problems with this approach include inefficency and weak independence between the hash function and the key. Uzgalis proposes a definition of General Hashing with the following properties: 1) independence of the key from the function is assumed, 2) the function is adequate (a change in any bit of the key will affect all bits of the hash key), and 3) given a hash key, it should be computationally difficult to discover a matching key. He argues that this is a better defitnition of hashing because now it is possible to discuss the probability of a bad hash, and we can develop algorithms to fit the description. One interesting theoretical question is whether a generalized hash function truly exists - this is interesting because if such a function exists, then a truly random number generator exists (a conjecture which most theorists do not believe). Finally, Uzgalis mentioned some interesting applications of hash functions, including: 1) balancing binary trees (more efficiently than AVL trees), 2) creating digests of content, and 3) random number generation. ----------------------------------- CS201 Summary #10 FUNCTIONAL PARTITIONING: A NEW APPROACH TO MULTI-PACKAGE PARTITIONING Frank Vahid, UC Irvine, Tuesday, May 27, 1997 Functional specifications of hardware, which are program-like descriptions of a digital system's behavior (e.g., VHDL) are becoming increasingly more popular. This enables a new approach to circuit partitioning, functional partitioning. In the traditional approach to partitioning (structural partitioning), a functional description (VHDL) is used by a behavioral synthesis tool to generate a structural netlist, which is then partitioned using a partiotioning algorithm (e.g., Kernighan-Lin based iterative algorithm). The functional partitioning approach applies partitioning to the functional specification, previous to the application of the behavioral synthesis engine. Intuitively, functional partitioning keeps closely related parts together, with the advantages that I/O is reduced, critical path crossings are reduced, and simpler circuits are generated. Perhaps most importantly, there is control over I/O at the functional level, and it is easy to trade off performance vs. I/O. Furthermore, it is possible to reduce synthesis tool runtimes by decomposing circuits into functional subsystems via functional partitioning. The difficulties in functional partitioning include the need for efficient, accurate, estimates of size, I/O, and performance. In contrast, structural approaches can use the very simple min-cut criteria to estimate the quality of the partitioining. Vahid showed the results of some experiments which demonstrate that the functional partitioning approach can yield significant advantages, including: reduction in I/O, improveed performance, and reduction in synthesis tool runtimes.