COP5570 term group project. ---------------------------------------------------------------------- Important dates: Project proposal: Nov. 1 Progress report: Nov. 15, Nov 29 Project presentation: Nov. 29 and 1 Project demo/software: Dec. 7 Project report: Dec. 7 ---------------------------------------------------------------------- Project objective: To apply the techniques learned in COP5570 to some research and/or practical applications. Type of projects: The potential projects can be broadly classified into two categories: applications (concurrent, threaded, parallel, distributed, and networked) and system support tools/libraries for applications. Grading: Grading will be based on six elements: project proposal biweekly progress reports, project presentation (final week of the class, project report, and project software and demo. Participation: 20% (proposal, biweekly progress reports, report, demo) Research and development: 80% (presentation + demo + software + report) The relative weight for research and development components will be determined based on the nature of the project. Projects with no significant research components should have significant development components. Research components: 1) The significance of the application or problem. (presentation + report) 2) The survey of the state of the art. (presentation + report) 3) The novelty of the proposed techniques (presentation + report) 4) The completeness of the implementation and evaluation (presentation + report) Development components: 1) Software usefulness and correctness (demo + software) 2) Software scope (demo + software) 3) The challenges/novelty of software implementation techniques (demo + software + presentation + report). 4) the completeness of the evaluation (presentation+report) biweekly progress reports: grade assigned by the instructor project presentation: grade assigned by classmates based on - clarity - organization - novelty - evaluation - overall research quality of the project - overall development quality of the project demo: grade assigned by the instructor software: grade assigned by the instructor project report: grade assigned by the instructor - clarity - organization - novelty - evaluation - overall writing - overall research quality of the project - overall development quality of the project ---------------------------------------------------------------------------- Examples of potential projects: 1. A full scale threaded/MPI (message passing) implementation of a UNIX utility. This project is mainly a development project. It seeks to leverage the increasing computing power in multi-core machines (threaded implementation) and distributed memory clusters (MPI implementation) to improve the efficiency of UNIX utility programs. Some candidates for this project are 'grep with the -R option', 'find', and 'make'. Research is needed to find out whether such implementations have been done before, to understand the full functionality to be supported, and to evaluate the newly developed program. For example, a tutorial for the 'find' utility can be found in http://www.softpanorama.org/Tools/Find/find_mini_tutorial.shtml. 2. Design, implement, and evaluate a threaded/MPI/distributed graph algorithm. Graph algorithms such as the spanning tree algorithm, the shortest path algorithm, the depth first search algorithm, are widely used in many applications. Such algorithms are usually quite concise in sequential form. Due to the proliferation of systems supporting parallelism, there is a push to develop parallel versions of graph algorithms for different types of platforms. In this project, you can pick any graph algorithm and survey existing work on this algorithm. You can then either implement/evaluate/compare variations of threaded/MPI/distributed graph algorithms, or develop/implement/evaluate a new algorithm. The study can be similar to the work in the following paper. D.A. Bader and G. Cong, ``A Fast, Parallel Spanning Tree Algorithm for Symmetric Multiprocessors (SMPs),'' Journal of Parallel and Distributed Computing, 65(9):994-1006, 2005. 3. Design, implement, and evaluate a threaded/MPI/distributed dense or sparse matrix algorithm. This project is similar to the previous one. You can pick any matrix algorithm, survey existing work on the algorithm. You can then either implement/evaluate/compare variations of threaded/MPI/distributed matrix algorithms, or develop/implement/evaluate a new algorithm (or a new implementation that has not been tried before). The study can be similar to the work in the following paper. Kai Shen, "Parallel Sparse LU Factorization on Different Message Passing Platforms," Journal of Parallel and Distributed Computing, 66(11):1387-1403, 2006. 4. Develop, implement, and evaluate a collective communication algorithm. Collective communication operations involve more than 2 parties. Developing efficient collective communication routines for large scale clusters have recently been a major challenge given the deployment of large scale clusters. In this project, you can select any collective communication operation, and develop new schemes (or implement and evaluate existing schemes). The main challenges in developing efficient collective communication algorithms for large scale clusters are that (1) network contention must be eliminated, and (2) communication start-up overheads must be minimized. P. Patarasuk and X. Yuan, "Bandwidth Optimal All-reduce Algorithms for Clusters of Workstations," Journal of Parallel and Distributed Computing, 69(2):117-124, Feb. 2009. 5. Parallel parsing and map drawing (suggested by Prof. Piyush Kumar). The map of the whole world in OpenStreetmap can be represented in a compressed file of about 4GB with a parallel compression tool bzip2. After the xml file is uncompressed, the total size would be about 100GB. Using the bzip2 tool, the uncompress process can be done in parallel, resulting in very fast uncompress speed. This creates a need to improve the speed for parsing the uncompressed file and creating a compact graph representation. This project seeks to extract the map information in parallel and to create the map in a compact form in parallel. This is a full application with algorithm issues (compact graph representations), systems issues (resource allocation and load balancing), and parallel programming issues. 6. Peer-to-peer on-line gaming The current online gaming has three server organization schemes: client-server, peer-to-peer, and public-server. Traditional on-line gaming uses the client-server architecture. Our connect-five server is one such example. The major problem of the client-server architecture is scalability: since the server must simulate all gaming activities, it is difficult to support a very large number of players. The peer-to-peer architecture is proposed to alleviate this limitation. The idea is to off-load the gaming activities to the clients (between players). In this project, a peer-to-peer gaming platform must be created. For example, you can extend the connect-five server and develop a client to support peer-to-peer connect-five game playing. One major issue in peer to peer game playing is cheating. Hence, the second part of the project would be to investigate some anti-cheating scheme in the peer-to-peer gaming platform. The following are the references to peer-to-peer gaming. Steven Daniel Webb, Sieteng Soh, and Willian Lau, "RACS: A Referee Anti-Cheat Scheme for P2P Gaming", NOSSDAV'2007. Steven Daniel Webb, Sieteng Soh, "Cheating in networked computer games - a review,"DIMEA'07. 7. Public server online gaming Another way to deal with the scalability issue in the client-server architecture is to use the public server architecture. The idea is to distribute the server load to multiple (public) servers by having all servers maintaining a cohesive gaming image. Server synchronization is the major issue in this approach. You can develop a public server gaming platform (e.g. extending our connect-five server to support public server architecture). A centralized mega-server is maintained that keeps track of the locations of all servers. When ever a server go up, it will join the the network of servers and allow players to do things across the server boundary. You can then investigate the server synchronization mechanisms ---------------------------------------------------------------------------