clarke@csri.toronto.edu (Jim Clarke) (01/09/89)
(SF = Sandford Fleming Building, 10 King's College Road)
(WB = Wallberg Building, 184 College Street)
(GB = Galbraith Building, 35 St. George Street)
SUMMARY:
AI SEMINAR - Thursday, January 26, 11 a.m. in Room SF 1105 -- Avi C. Kak
"Research Issues in 3-D Robotic Vision"
SYSTEMS SEMINAR - Thursday, January 26, 11 a.m. in Room WB 342 -- Mary K. Vernon
"Performance Analysis of the Wisconsin Multicube"
THEORY SEMINAR - Thursday, January 26, 3 p.m. in Room GB 244 -- Allan Borodin
"Towards a Theory of Competitive Analysis for On-line Algorithms"
-----------------------
AI SEMINAR - Thursday, January 26, 11 a.m. in Room SF 1105
Avi C. Kak
Purdue University
"Research Issues in 3-D Robotic Vision"
The speaker will first survey the state-of-the-art in passive approaches to
3-D robotic vision, emphasizing what has been done so far in binocular
stereopsis for depth perception. The deficiencies of the purely bottom-up
approaches will be highlighted and the limitations of what we currently
know about injecting high-level object knowledge into the algorithms point-
ed out. A rule-based approach for integrating the various paradigms for bi-
nocular stereopsis will also be discussed.
The second half of the talk will focus on active approaches, especially
those employing structured-light and laser-radar for depth perception. The
speaker will mention the computational complexity issues involved in
model-based object interpretation strategies. The subject of modeling 3-D
objects will also be broached. Finally, the speaker will address the topic
of recognizing generic 3-D shapes.
______________________________
About the speaker:
Avi Kak, a professor of electrical engineering at Purdue, is currently en-
gaged in research in various issues dealing with robotic intelligence. In
particular, he is interested in reasoning architectures for solving spatial
problems, development of planners capable of transforming human supplied
assembly plans into robotic manipulations in a sensor-based environment,
robot vision, etc. He has coauthored the two-volume book Digital Picture
Processing, published by Academic Press, and the Principles of Computerized
Tomographic Imaging, published by the IEEE Press.
_____________________________
SYSTEMS SEMINAR - Thursday, January 26, 11 a.m. in Room WB 342
Mary K. Vernon
University of Wisconsin - Madison
"Performance Analysis of the Wisconsin Multicube"
The Wisconsin Multicube is a new large-scale multiprocessor architecture
currently under investigation at the University of Wisconsin - Madison. A
key characteristic of the machine is that it is based on shared buses and a
snooping cache coherence protocol. The organization of the shared buses
and shared memory is unique and non-hierarchical. The two-dimensional ver-
sion of the architecture is envisioned as scaling to 1024 processors. This
talk will describe the architecture, a preliminary performance analysis of
the system using a modeling technique called "Customized Mean Value
Analysis", and recently designed hardware support for synchronization
events. The talk will also cover a formal argument by Goodman, Hill, and
Woest that the macihien is scalable. The performance analysis addresses
the issues of optimal cache block size, optimal size of the two- dimension-
al Multicube, the effect of broadcast invalidations on system performance,
and the viability of several hardware techniques for reducing the latency
of remote memory requests.
THEORY SEMINAR - Thursday, January 26, 3 p.m. in Room GB 244
Allan Borodin
University of Toronto
"Towards a Theory of Competitive Analysis for On-line Algorithms"
In [CACM, Feb 85] Sleator and Tarjan considered the efficiency of various
paging strategies (e.g. LRU, FIFO) as well as the move to front strategy
for maintaining a list. The novel aspect of that approach was to compare
the cost incurred by an on-line algorithm against the optimal off-line
cost. In [STOC, 86] Borodin, Linial and Saks introduced task systems, an
abstract framework for studying on-line algorithms. Manasse, McGeoch and
Sleator [STOC, 87] introduced the K-server (and K server with excursions)
problem, another abstract framework which generalizes the paging problem.
We will discuss the BLS and MMS settings and show how the K-server problem
(but not the K-server with excursions) can be viewed as a task system. We
shall argue that while the task system model is generally too abstract to
obtain good bounds, it can be useful in terms of suggesting results. For
example, we will discuss recent results (Fiat, et al., Raghavan and Snir)
on randomized paging algorithms.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
BITNET,CSNET: clarke@csri.toronto.edu CDNNET: clarke@csri.toronto.cdn
UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke