📄 http:^^www.cs.cornell.edu^info^courses^spring-96^cs516^proj-idea.html
字号:
MIME-Version: 1.0
Server: CERN/3.0
Date: Monday, 16-Dec-96 23:50:59 GMT
Content-Type: text/html
Content-Length: 12013
Last-Modified: Thursday, 14-Mar-96 18:00:20 GMT
<html><head><title>CS516 Project Proposals</title></head><body><h1>CS 516 Project Proposals</h1> <h2>Thorsten von Eicken</h2><h3>Wednesday, Mar. 13th, 1996</h3> <hr><h2>Proposals</h2><h3>SP-2 related projects:</h3><OL><p><li><h3>Splash benchmarks in CC++ on the SP-2</h3>Splash is a benchmark suite consisting of parallel applications forshared memory machines developed at Stanford. Splash-2 is the latestversion of Splash containing several new applications as well as theoriginal ones. The suite is divided into two categories: kernels andapplications. Kernels are routines commonly used by applications.Here is a sample of them:<p>Kernels: Complex 1D FFT;Blocked LU Decomposition;Blocked Sparse Cholesky Factorization;Integer Radix Sort;<p>Applications:Barnes-Hut;Ocean Simulation;Water Simulation with Spatial Data Structure;Water Simulation without Spatial Data Structure;and others.<p>Implement the kernels listed above and one or two applications(depending on the level of difficulty) in CC++ or Split-C. Yourimplementation will be judged on correctness and performance. Acareful explanation of the results is expected along with detailedtiming breakdowns.<p>The source code of the benchmarks for shared memory machines isavailable on the Web. You can choose to port the existing code toCC++ or Split-C, or write your own from scratch once you understandthe problem. You should also read the paper entitled "Splash-2Programs: Characterization and Methodological Considerations"published in ISCA'95. All these can be obtained from the Web.<p>This project will expose you to parallel programming usingstate-of-the-art languages in both shared and distributed memorymachines. The Splash benchmarks are widely accepted in the researchcommunity. Besides, CC++ is a parallel extension of C++ that hasbecome very popular over the years. You can do your project on anyavailable platform, but we suggest the SP-2 because these languagesare currently well supported by us.<p><li><h3>PVM over Active Messages on the SP-2</h3>PVM (Parallel Virtual Machine) is a very popular software package that supportsparallel computing on networked of workstations. It provides a userlibrary with routines (e.g. pvm_send, pvm_recv) for communication between processes. PVM communication is baed on TCP/UDP protocols, hence onlycoarse-grained parallel applications can get reasonable performance.<p>Try improve the performace of PVM by implementing its major communication routines over Active Messages on the SP-2 and benchmark them againstSplit-C as well as MPI.<p><li><h3>Parallel VMRL renderer on the SP-2, in Split-C or CC++</h3>Implement a parallel renderer for the VRML (virtual reality modellinglanguage). This would allow very complex VRML documents to be downloadedand scenes rendered, hopefully in near-real-time, on a system such as the SP-2. You would also need a way to send the rendered image quicklyto some desktop workstation ... a simple X connection works for prototype,but what about sending the rendered image back over ATM? <p><li><h3>A parallel POVray or other raytracer in Split-C or CC++ </h3>Implement a parallel POVray or other raytracer. This is similar to theabove, but probably has a less "real-time" feel (unless you manage to doit VERY quickly). POVRay is a freely available raytracing package whichruns on a wide range of UNIX systems; try parallelizing aspects of it(say, by dividing the rendering space between CPUs) and implementing ona system such as the SP-2.<p><li><h3>A parallel file system on SP-2</h3>Implement a parallel file system on top of the regular filesystem on eachnode. This is most easily done as a user-level library within Split-C.<p><li><h3>Split-C benchmark comparison and survey</h3>All of the high-end parallelsystems in the department can run programs written in the Split-C parallellanguage: The SP-2, ATM cluster, Fast Ethernet cluster, and multiprocessorSPARCs. The Berkeley and UCSB groups have a number of nice Split-C benchmarks; we would like to get an understanding for their relativeperformance on all of the above systems, as well as how they scale (say,when running with 8 as opposed to 4 CPUs).<p><li><h3>Linda over Active Messages on the SP-2</h3>Linda is a simple (only six operations!) yet powerful extension to existing sequential languages that allows parallel execution of programs. The computingmodel is slightly different from what you've been shown so far in the course.Messages and new tasks to be executed are put into a tuple spaceand they can be retrieved from there by any process. One does not haveto specify the address of a sender of receiver -- the tuple space is sharedbetween all processes. Reception of messages is based on pattern matching. Based on the simple concept of tuple space, one can programall kinds of synchronization, blocking and non-blocking communication, point-to-point or multicast message passing etc.<p>The project will be to implement Linda run-time system over Active Messageson the SP-2, as an extension to C. The work will include understandingof Linda model and using fast communication subsystem and threads in orderto get very efficient run-time system. </OL><h3>U_Net related projects:</h3><p>These projects specifically deal with U-Net, our system for low-latencyuser-level networking. Four implementations of U-Net exist (three forATM cards, one for Fast Ethernet). In these projects you will augment theexisting U-Net system, either on one of these implementations, orcombining several of them.<OL><p><li><h3>CUsee-me over the ATM network or over Fast Ethernet</h3>Implement and demo a high-speed version of CUSeeMe over the ATM networkor over Fast Ethernet. Requires independence, since nobody in our group knows how CUSeeMe works. The idea here is to explore methods of long-range video teleconferencing using the U-Net approach. As opposed tosending video between two workstations side-by-side with an ATM fiberbetween them, how can protocols be designed for robust, multicast video conferencing? <p>An alternative to CUSeeMe would be a system such as the MBONE using 'vat',or some other 'free' video conferencing package such as ivs.<p><li><h3>Gateway between Fast Ethernet and ATM using U-Net</h3>Design and build a gateway between Fast Ethernet and ATM using U-Net.This can either be at the raw U-Net level or at the IP level.<p><li><h3>Kernel Endpoint for U-Net</h3>One 'problem' with U-Net is that it doesn'tallow existing applications and kernel facilities to easily share thenetwork device with U-Net. The idea is to implement a kernel-levelU-Net endpoint where data generated from IP sockets (in the kernel) issent and received through the endpoint. In this way you are treating thekernel endpoint as a kind of Ethernet driver (say). <p>While any communication using the kernel endpoint will no doubt beslower than user-level endpoints, the idea is to allow many applicationsto multiplex on one kernel endpoint and for existing socket-based appsto at least run. You would not need to implement IP or other high-levelprotocols; essentially you would replace the low-level kernel functionsfor sending data to an ATM or Ethernet card with routines which read/writeto the kernel endpoint.<p>The best platform for this is the ATM or Fast Ethernet implementation of U-Net on Linux. <p>This is an "expert" project best undertaken by someone with Linux kernelhacking experience.<p><li><h3>IP packet filter on SBA-200 ATM adapter</h3>U-Net over Fast Ethernet and ATM currently use a simple "protocol" which is not compatible with IP. Implement a simple IPv4 packet filterfor either U-Net for Fast Ethernet or ATM, so that packets are in thecorrect IPv4 format. You may not wish to implement all aspects of theIP protocol, but that would be a plus.<p><li><h3>Flow control for Active Messages on Fast Ethernet</h3>Fast Ethernet poses interesting flow control problems because acks competewith regular packets for bandwidth. Design a good flow control algorithmfor Active Messages that works well on a shared medium fast ethernet.<p><li><h3>Fast RPC</h3>Pick up last year's Fast RPC project and actually make it work.<p><li><h3>Distributed Shared Memory</h3>Pick up last year's DSM project, make it work and run the Splash benchmarksover it.<p><li><h3>Network performance tool Netperf for U-Net</h3>Implement the standard network performance tool Netperf for U-Net<p><li><h3>Gang Scheduling for the U-Net Cluster</h3>In gang scheduling,all processors working on a single parallel application schedule themselves synchronously, so that communication and computation phasescan be coordinated and reduce latency for data exchange. This mightrequire some kind of interesting modifications to the kernel scheduler,and some sort of "clock synchronization" so that all processes in, say,a Split-C application run at the same time across the network of machines.<p>This is an "expert" project best undertaken by someone with Linux kernelhacking experience.</OL><h3>USIT related projects:</h3>USIT is a toolkit we developed to help build parallel and distributedprogramming environment on the ATM cluster. Currently, there are utilityprograms to set up daemons on a set of machines within the cluster, andto start running split-c programs and forwarding I/O between your localmachine and the cluster. Those who will be using the cluster to runsplit-c programs and other application programs may also find thetoolkit useful.<p>At a lower level, USIT provides both C and Tcl/Tk interfaces for jobcontrol, I/O forwarding, job scheduling, U-Net channel allocation etc. withinthe cluster. These interfaces can be used to customize a particularexecution environment your application requires.<OL><p><li><h3>PVM over U-Net using USIT</h3>PVM is a popular software package that allows a heterogeneous networkof parallel and serial computers to appear as a single concurrent computationalresource. PVM consists of two parts: daemon processes that users installon machines that use PVM, and a user library mainly for communication betweenprocesses.In this project, you are to explore the possibility of implementing basic PVM daemon functionalities on U-Net using the interfaces USIT provides, and if necessary implement additionalinterfaces for USIT.</OL><h3>Other:</h3><OL><p><li><h3>Benchmark the Liedtke microkernel system</h3>Jochen Liedtke published the paper "On microkernel construction"in last SOSP. The abstract is included below. The project will beto read the paper thoroughly, understand the problems and proposedsolutions, download the described code and benchmark it.<p>Abstract:From a software-technology point of view, the microkernel concept is superior to large integrated kernels. On the other hand, it is widely believed that (a) microkernel based systems are inherently inefficient and (b) they are not sufficiently flexible. Contradictory to this belief,we show and support by documentary evidence that inefficiency and inflexibility of current microkernels is not inherited from the basic idea but mostly from overloading the kernel and/or from improper implementation.Based on functional reasons, we describe some concepts which must be implemented by a microkernel and illustrate their flexibility. Then, we analyze the performance critical points. We show what performanceis achievable, that the efficiency is sufficient with respect to macro-kernels and why some published contradictory measurements are not evident. Furthermore, we describe some implementation techniques and illustrate why microkernels are inherently not portable, although they improve portability of the whole system.</OL><br><br><hr><br><a href="../Welcome.html">Return to CS 516 Home Page</a><p><hr></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -