NDLI: The Multi-Processor Scheduling Problem in Phylogenetics

Content Provider	IEEE Xplore Digital Library
Author	Jiajie Zhang Stamatakis, A.
Copyright Year	2012
Abstract	Advances in wet-lab sequencing techniques allow for sequencing between 100 genomes up to 1000 full transcriptomes of species whose evolutionary relationships shall be disentangled by means of phylogenetic analyses. Likelihood-based evolutionary models allow for partitioning such broad phylogenomic datasets, for instance into gene regions, for which likelihood model parameters (except for the tree itself) can be estimated independently. Present day phylogenomic datasets are typically split up into 1000-10,000 distinct partitions. While the likelihood on such datasets needs to be computed in parallel because of the high memory requirements, it has not yet been assessed how to optimally distribute partitions and/or alignment sites to processors, in particular when the number of cores is significantly smaller than the number of partitions. We find that, by distributing partitions (of varying lengths) monolithically to processors, the induced load distribution problem essentially corresponds to the well-known multiprocessor scheduling problem. By implementing the simple Longest Processing Time (LPT) heuristics in the PThreads and MPI version of RAxML-Light, we were able to accelerate run times by up to one order of magnitude. Other heuristics for multi-processor scheduling such as improved MultiFit, improved Zero-One, or the Three Phase approach did not yield notable performance improvements.
Starting Page	691
Ending Page	698
File Size	555541
Page Count	8
File Format	PDF
ISBN	9781467309745
DOI	10.1109/IPDPSW.2012.86
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-05-21
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Program processors Processor scheduling Computational modeling Phylogenetics RAxML-Light Scheduling Partitioning algorithms Phylogeny Mathematical model Standards
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Dynamic task scheduling for the Uintah framework

Efficient algorithm for DAG scheduling on multi-clusters platforms

Buffer minimization in pipelined SDF scheduling on multi-core platforms

New Model and Genetic Algorithm for Multi-Installment Divisible-Load Scheduling

OpenMP-based Parallel Algorithms for Solving Kronecker Descriptors

Scheduling CPU-Intensive Grid Applications Using Partial Information

Energy-Aware Partitioned Fixed-Priority Scheduling for Chip Multi-processors

Simulation-based evaluation of real-time multiprocessor scheduling strategies

Multi-criteria evaluation of partitioning schemes for real-time systems

The Multi-Processor Scheduling Problem in Phylogenetics

Similar Documents

Dynamic task scheduling for the Uintah framework

Efficient algorithm for DAG scheduling on multi-clusters platforms

Buffer minimization in pipelined SDF scheduling on multi-core platforms

New Model and Genetic Algorithm for Multi-Installment Divisible-Load Scheduling

OpenMP-based Parallel Algorithms for Solving Kronecker Descriptors

Scheduling CPU-Intensive Grid Applications Using Partial Information

Energy-Aware Partitioned Fixed-Priority Scheduling for Chip Multi-processors

Simulation-based evaluation of real-time multiprocessor scheduling strategies

Multi-criteria evaluation of partitioning schemes for real-time systems

The Multi-Processor Scheduling Problem in Phylogenetics