Towards an Architecture-Independent Analysis of Parallel Algorithms
From MaRDI portal
Publication:3034819
DOI10.1137/0219021zbMath0692.68032OpenAlexW1989582918MaRDI QIDQ3034819
Mihalis Yannakakis, Christos H. 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
Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Theory of operating systems (68N25)
Related Items (38)
Three, four, five, six, or the complexity of scheduling with communication delays ⋮ Performance bounds for column-block partitioning of parallel Gaussian elimination and Gauss-Jordan methods ⋮ New complexity results on scheduling with small communication delays ⋮ Parallel Machine Scheduling with Uncertain Communication Delays ⋮ Benchmarking the clustering algorithms for multiprocessor environments using dynamic priority of modules ⋮ AN ALGORITHMIC MODEL FOR HETEROGENEOUS HYPER-CLUSTERS: RATIONALE AND EXPERIENCE ⋮ Scheduling tree dags on parallel architectures ⋮ Unnamed Item ⋮ Approximating schedules for dynamic process graphs efficiently ⋮ Sensitivity bounds for machine scheduling with uncertain communication delays ⋮ Using duplication for scheduling unitary tasks on m processors with unit communication delays ⋮ Data transmission in processor networks ⋮ Malleable scheduling beyond identical machines ⋮ Unnamed Item ⋮ How to pack directed acyclic graphs into small blocks ⋮ Optimizing latency and throughput of application workflows on clusters ⋮ ECP: a novel clustering-based technique to schedule precedence constrained tasks on multiprocessor computing systems ⋮ Complexity and approximation for precedence constrained scheduling problems with large communication delays ⋮ List scheduling with duplication for heterogeneous computing systems ⋮ Reliability-aware scheduling strategy for heterogeneous distributed computing systems ⋮ Scheduling trees with large communication delays on two identical processors ⋮ Scheduling with uncertainties on new computing platforms ⋮ Scheduling \(UET\)-tasks on a star network: complexity and approximation ⋮ Communication contention in APN list scheduling algorithm ⋮ Some models for scheduling parallel programs with communication delays ⋮ Polynomial time approximation algorithms for machine scheduling: Ten open problems ⋮ Task scheduling with and without communication delays: A unified approach ⋮ On the complexity of scheduling with large communication delays ⋮ Computing the execution probability of jobs with replication in mixed-criticality schedules ⋮ Scheduling Precedence Task Graphs with Disturbances ⋮ Scheduling inverse trees under the communication model of the LogP-machine ⋮ Scheduling 2-dimensional grids with large communication delays ⋮ CLUSTER-BASED TASK SCHEDULING FOR THE LOGP MODEL ⋮ GUIDELINES FOR DATA-PARALLEL CYCLE-STEALING IN NETWORKS OF WORKSTATIONS II: ON MAXIMIZING GUARANTEED OUTPUT ⋮ ON MESSAGE PACKAGING IN TASK SCHEDULING FOR DISTRIBUTED MEMORY PARALLEL MACHINES ⋮ On scheduling send-graphs and receive-graphs under the LogP-model ⋮ A very difficult scheduling problem with communication delays ⋮ Two-way dominant sequence clustering for processor scheduling
This page was built for publication: Towards an Architecture-Independent Analysis of Parallel Algorithms
