CSE 8383 - Advanced Computer ArchitectureContentsGroup WorkWhat?ExplainPowerPoint PresentationLeopold’s View of the FieldParallel and Distributed Architecture (Leopold, 2001)Slide 9What is a Cluster?ClustersClusters offer these featuresHigh Performance ClustersCluster ComponentsCluster Architecture and OSCluster SizeTypical Cluster EnvironmentPVM & MPIPVM IntroductionPVM EnvironmentPVM SoftwarePVM ApplicationPVM Application (Cont.)Application StructureTask CreationTo Create a child, you must specify:Task IDTask ID RetrievalSlide 29SchedulingSlide 31Introduction to SchedulingScheduling SystemProgram TasksTask GraphMachineExamples of Network GraphsTask ScheduleGantt ChartExecution and Communication TimesComplexitySlide 42What is Driving Mobile ComputingMobile ComputingMobility versus NomadicityMain ComponentsWired BackboneWireless Multi-hop BackboneHybrid backboneIETF Mobile IPMobile IP (Cont.)Slide 52Update in Mobile IPTwo-Tier UpdateTradeoff Between Update and SearchCSE 8383 - Advanced Computer ArchitectureWeek-13April 15, 2004engr.smu.edu/~rewini/8383ContentsWarm upBig PictureClustersSchedulingMobile IPReliability issues in Mobile IPLet’s test your network backgroundGroup WorkWhat?ApplicationPresentationSessionTransportNetworkData LinkPhysicalApplicationPresentationSessionTransportNetworkData LinkPhysicalLANLANInternetInternetExplainApplicationPresentationSessionTransportNetworkData LinkPhysicalMailftpTelnetTransmission Control Protocol (TCP)Internet Protocol(IP)EthernetToken ringBig PictureLeopold’s View of the FieldNumerous Application ProgramsConcrete ArchitecturesPthreads Java ThreadsOpenMPSkeletonsMPIPVMThreadsShared MemoryMessage PassingDistributed SMClusterSMP CC-NUMA ATMMyrinetHiding DetailsHighLowParallel and Distributed Architecture (Leopold, 2001)Degree of CouplingSIMD MIMDShared MemoryDistributed MemorySupported Grain SizesCommunication SpeedslowfastfinecoarseloosetightSIMD SMP CC-NUMA DMPC Cluster GridClusters(Commodity Off The Shelf)What is a Cluster?A Collection of interconnected stand-alone computers working working together as a single integrated computing resourceCluster nod3es may exist in a single cabinet or be physically separated and connected via a LANClustersMCPI/OOSMCPI/OOSMCPI/OOSMiddlewareProgramming EnvironmentInterconnection NetworkClusters offer these featuresHigh PerformanceExpandability and ScalabilityHigh ThroughputHigh AvailabilityHigh Performance ClustersTuned to derive maximum performanceShare processing loadNeeds software customizationE.g. BeowulfCluster ComponentsHomogeneous ClustersAll nodes have same configurationHeterogeneous ClustersNodes with different configurations e.g. different OSsCluster Architecture and OSCluster of PCsCluster of WorkstationsCluster of SMPs (Symmetric Multiprocessors)Linux clusters (Beowulf)Solaris clusters (NOW)NT clustersCluster SizeGroup clusters – 2-99 nodesDepartmental clusters – 99-999 nodesOrganizational clusters – many 100’sGlobal clusters – 1000’s +Internet wideTypical Cluster EnvironmentUser ApplicationPVM/MPIOS/HardwareMiddlewarePVM & MPIPVM (Parallel Virtual Machine)Allows heterogeneous collection of computers linked by a network to be used as a single large parallel computerMPI (Message Passing Interface)Library specification for message passingFree and vendor supplied implementations availablePVM Introductionhttp://www.netlib.org/pvm3/http://www.epm.ornl.gov/pvm/Started as a research project in 1989Developed at Oak Ridge National Lab & University of TennesseeIt makes it possible to develop applications on a set of heterogeneous computers connected by a network that appears logically to user as a single parallel computerPVM EnvironmentVirtual machineDynamic set of heterogeneous computer systems connected via a network and managed as a single parallel computerComputer nodes  hostsHosts are uniprocessors or multiprocessors running PVM softwarePVM SoftwareTwo Components:Library of PVM routinesDaemonShould reside on all hosts in the virtual machineBefore running an application, the user must start up PVM and configure a virtual machinePVM ApplicationA number of sequential programs, each of which will correspond to one or more processes in a parallel programThese programs are compiled individually for each host in the virtual machineObject files are placed in locations accessible from other hostsPVM Application (Cont.)One of these sequential programs, which is called the initiation task, has to be started manually on one of the hostsTasks on other hosts are started automatically by the initiation taskTasks comprising a PVM application can be identical (SPMD) [common in most applications] or can be different (pipeline: input processing, output)Application StructureStart graphMiddle node is call supervisor or masterSupervisor-workers or Master-slavesTreeRoot is the top supervisorHierarchyTask CreationA task in PVM can be started manually or can be spawned from another taskThe function pvm_spawn() is used for dynamic task creation.The task that calls the function pvm_spawn() is referred to as the parentThe newly created tasks are called children.To Create a child, you must specify: 1. The machine on which the child will be started2. A path to the executable file on the specified machine3. The number of copies of the child to be created4. An array of arguments to the child tasksTask IDAll PVM tasks are identified by an integer task identifierWhen a task is created it is assigned a unique identifier (TID)Task identifiers can be used to identify senders and receivers during communication. It can also be used to assign functions to different tasks based on their TIDsTask ID RetrievalTask’s TID  pvm_mytid()Mytid = pvm_mytid;Child’s TID  pvm_spawn()pvm_spawn(…,…,…,…,…, &tid);Parent’s TID  pvm_parent()my_parent_tid = pvm_parent();Daemon’s TID  pvm_tidtohost()daemon_tid = pvm_tidtohost(id);SchedulingPartitioner Grains of Sequential CodeParallel/Distributed SystemParallel Program TasksSchedulerScheduleProcessorsTimeProgram TasksSequential ProgramExplicit ApproachImplicit ApproachDependence Analyzer Ideal ParallelismSchedulingSchedulingIntroductionModelProgram tasksMachineScheduleExecution and communication timeProblem