Towards an Architecture-Independent Analysis of Parallel Algorithms

DOI10.1137/0219021zbMATH Open0692.68032OpenAlexW1989582918MaRDI QIDQ3034819FDOQ3034819

Authors: Mihalis Yannakakis, Christos Papadimitriou 

Publication date: 1990

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0219021

Recommendations

• scientific article; zbMATH DE number 1728436
• Architecture independent parallel algorithm design: theory vs practice
• scientific article; zbMATH DE number 108570
• scientific article; zbMATH DE number 53193
• scientific article; zbMATH DE number 4020458
• Towards structured parallel computing on architecture-independent parallel algorithm design for distributed-memory architectures
• scientific article; zbMATH DE number 729658
• Practical considerations of parallel simulations and architecture independent parallel algorithm design
• scientific article; zbMATH DE number 107950

zbMATH Keywords

approximation algorithmparallel computationschedulingcommunication delaymultiprocessing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Theory of operating systems (68N25)

Cited In (50)

• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• How to pack directed acyclic graphs into small blocks
• Scheduling with uncertainties on new computing platforms
• ECP: a novel clustering-based technique to schedule precedence constrained tasks on multiprocessor computing systems
• New complexity results on scheduling with small communication delays
• On scheduling send-graphs and receive-graphs under the LogP-model
• A very difficult scheduling problem with communication delays
• Scheduling 2-dimensional grids with large communication delays
• Title not available (Why is that?)
• Scheduling with duplication on \(m\) processors with small communication delays
• Guidelines for data-parallel cycle-stealing in networks of workstations. II: On maximizing guaranteed output
• Complexity and approximation for precedence constrained scheduling problems with large communication delays
• Some models for scheduling parallel programs with communication delays
• Task scheduling with and without communication delays: A unified approach
• List scheduling with duplication for heterogeneous computing systems
• Title not available (Why is that?)
• On high level characterization of parallelism
• Sensitivity bounds for machine scheduling with uncertain communication delays
• CLUSTER-BASED TASK SCHEDULING FOR THE LOGP MODEL
• On the complexity of scheduling with large communication delays
• Three, four, five, six, or the complexity of scheduling with communication delays
• Scalable heuristic algorithms for the parallel execution of data flow acyclic digraphs
• Scheduling inverse trees under the communication model of the LogP-machine
• Optimizing latency and throughput of application workflows on clusters
• Data transmission in processor networks
• Analysis of the Parallel Distinguished Point Tradeoff
• Approximating schedules for dynamic process graphs efficiently
• Scheduling \(UET\)-tasks on a star network: complexity and approximation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Malleable scheduling beyond identical machines
• Communication contention in APN list scheduling algorithm
• A method for estimating resources required for implementation of finite algorithms
• Two-way dominant sequence clustering for processor scheduling
• On message packaging in task scheduling for distributed memory parallel machines
• Computational force: a unifying concept for scalability analysis
• Benchmarking the clustering algorithms for multiprocessor environments using dynamic priority of modules
• AN ALGORITHMIC MODEL FOR HETEROGENEOUS HYPER-CLUSTERS: RATIONALE AND EXPERIENCE
• Performance bounds for column-block partitioning of parallel Gaussian elimination and Gauss-Jordan methods
• Computing the execution probability of jobs with replication in mixed-criticality schedules
• Title not available (Why is that?)
• Scheduling tree dags on parallel architectures
• Scheduling Precedence Task Graphs with Disturbances
• Bounds and algorithms for a practical task allocation model (extended abstract)
• Using duplication for scheduling unitary tasks on m processors with unit communication delays
• Architecture-independent parallelism for both shared- and distributed-memory machines using the Filaments package
• Reliability-aware scheduling strategy for heterogeneous distributed computing systems
• Scheduling trees with large communication delays on two identical processors
• Multilevel algebraic approach for performance analysis of parallel algorithms
• Parallel Machine Scheduling with Uncertain Communication Delays

This page was built for publication: Towards an Architecture-Independent Analysis of Parallel Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3034819)