Parallel And Distributed Computing
- CSCI 6175 Seminar in Computer Science

Xiannong Meng
Department of Computer Science
The University of Texas - Pan American
Edinburg, TX 78539-2999
meng@panam.edu

Fall 1997

Outline of the Presentation

• What is parallel computing? What is distributed computing?
• Parallel computing
  • Problems
  • Tools and national centers
  • Trends
• Internet-based computing
  • SuperWeb
  • Issues and efforts
• Distributed simulation
  • Conservative and optimistic approaches
  • Web-based simulation
• Further probes

Parallel And Distributed Computing

• Parallel computing partitions a task into subtasks each of which has the same the computing.
• Parellel computing often involves data parallel (SIMD); shared memory address space.
• Example: stacking books into bookshelves in a library.
• Distributed computing partitions a task into subtasks each of which may have a different computing task, collectively they accomplish a task.
• Distributed computing often assumes autonomous computing agents; they often do not share memory address space; communications are done through message passing.
• Example: a library has to have a circulation desk, a reference librarian, a stacking staff put the books back to the shelves. each subtask
• The difference between parallel and distributed computing is blurring.

Parallel Computing

• Grand Challenge Problems: in 1993, NSF and a group of scientists proposed the Grand Challenge Problems which are the problems that require tera-flop computing power. The problems range from environmental and earth science to computational physics.

  Examples include

  • large scale environmental model
  • large scale structure and galaxy formation
  • computational quantum materials
  • data analysis and knowledge discovery in geophysical databases
• NSF has founded a number of meta-computer centers, along with a number of established national laboratories to attack these Grand Challenge Problems.
• Non-government organizations such as Parallel Tools Consortium also play important roles in the evolving of parallel computing technology.
• Major software tools available: PVM (Parallel Virtual Machine) and MPI (Message Passing Interface)
• Move towards the utilization of computing power available over the Internet.

Internet-Based Computing

• Estimated more than 30 million computers will be connected to the Internet by the end of 1997
• Most of the computers are used at most half of the time
• Each individual computer may not be as fast, but the combined computing power can be enormous
• Based on these observations, some researchers proposed ``SuperWeb'', a global Web-based parallel computing infrastructure
• Key ideas:
  • There are three kinds of computers in SuperWeb: hosts, brokers, and clients.
  • Hosts offer their resources (CPU time, memory, storage) as a commodity by registering with a broker.
  • Brokers coordinate the supply and demand for computing resources.
  • Clients are users or computers that need extra computational resources.

• Hosts register their excessive resources with brokers by sending messages to a broker. By registering with a broker, the host becomes a part of the SuperWeb.
• Brokers:
  • they are responsible for
    • Registering hosts
    • Accepting client requests
    • Overseeing client/host interaction
  • A broker consists of three modules: the interface, the scheduler, and the accouting module.
    • Interface: hosts and clients register through this interface, e.g. use a form to fill out host/client information.
    • Scheduler: assign incoming tasks to available resources.
    • Accounting: keep track of the charges incurred by clients, and credites gained by hosts.
• Clients request resource through a broker. When the request is granted, the client contacts the hosts directly for computing power. When the computing is completed, the client disconnects itself from the hosts.
• Economic model: the hosts can be rewareded for providing their spare resources by allowing free use of other's CPU, storage space, license etc.

• Difficulties in Web-based computing come from two major sources
  • Technically: security (solution: encrypted computing) and speed of communicaiton
  • Socially: why letting others use my spare computing resources? (solution: commodity exchange, coupon for other items) How can I trust the foregn programs running on my computer?

Distributed Simulations

One of the interesting applications of Internet-based computing is distributed simulation.

• Discrete event driven simulation
• Parallel and distributed simulation
• Local Causality Constraint: Events are processed in a non-decreasing timestamp order.
• Conservative approach: make sure no causality is violated;
• Optimistic approach: each logical process can advance at its own pace. When causality error is detected, a rollback is carried out to recover the errors.
• We concentrate on optimistic distributed simulation of discrete event systems.
  • Logical process: they can be on the same processor or different processor
  • Event list: they can be implemented in any priority list
  • Distributed event list

  • Time Warp
    • GVT
    • rollback
    • anti-event (message)

Web-Based Simulation

• Java and its applets
• Key ideas in Web-based simulation:
  • Interactive
  • Animation
  • Heterogeneous environment

For Further Information

• A.D. Alexandrov, M. Ibel, K.E. Schauser, and C.J. Scheiman, ``SuperWeb: Towards a Global Web-Based Parallel Computing Infrastructure'', <http://www.cs.ucsb.edu/~schauser/papers/>, April 1997
• A.D. Alexandrov, M. Ibel, K.E. Schauser, and C.J. Scheiman, ``SuperWeb: Research Issues in Java-Based Global Computing'',

  <http://www.cs.ucsb.edu/~schauser/papers/>, June 1997

• E.H. Page, R.L. Moose Jr., S.P. Griffin, ``Web-Based Simulation in SimJava Using Remote Method Invocation'', Proceedings of 1997 Winter Simulation Conference, December 1997, Atlanta, GA
• R. McNab and F.W. Howell, ``Using Java for Discrete Event Simulation'', Proceedings of Twelfth UK Computer and Telecommunications Performance Engineering Workshop, 1996, University of Edinburgh
• R. Fujimoto, ``Parallel And Distributed Simulation'',

  <http://www.cs.gatech.edu/Computing/Pads/pads-intro.ps>, October 1997

• E. Page, ``A Survey of Web-Based Simulation''

  <http://ms.is.org/websim/survey/survey.html>

• P. Fishwick, ``Paul Fishwick Computer Simulation''

  <http://www.cise.ufl.edu/~fishwick/>

• P.S. Pacheco, ``Parallell Programming with MPI'', Morgan Kaufmann Publisher, 1997
• X. Meng, ``CSCI 6356: Parallel Computing Courseware'',

  <http://www.cs.panam.edu/~meng/Course/CS6356/>

• About this document ...