On the parallel complexity of loops

DOI10.1016/S0304-3975(96)00184-3MaRDI QIDQ1391751zbMATH OpenOpenAlexFDO

Authors Oscar H. Ibarra, Nicholas Q. Tran, Tao Yang

Publication date 22 July 1998

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(96)00184-3

zbMATH Keywords

PRAM complexity theory

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Scheduling Sequential Loops on Parallel Processors
• Optimal code parallelization using unimodular transformations
• Parallel execution of program loops
• Publication:4735042
• Fine-grain parallelization of imperfectly nested loops

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 41792 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 194119 (Why is no real title available?)
• scientific article; zbMATH DE number 10089 (Why is no real title available?)
• A taxonomy of problems with fast parallel algorithms
• Alternation
• An extension of Savitch's theorem to small space bounds
• Complete problems for deterministic polynomial time
• Efficient recognition of rational relations
• Nondeterministic Space is Closed under Complementation
• On tape-bounded complexity classes and multihead finite automata
• On uniform circuit complexity
• Parallel complexity of logical query programs
• Some classes of languages in \(NC^ 1\)

Cited in

(11)

• scientific article; zbMATH DE number 5885666 (Why is no real title available?)
• Auto recognition of ParDo loops in the program
• scientific article; zbMATH DE number 2113582 (Why is no real title available?)
• Fine-grain parallelization of imperfectly nested loops
• ON THE OPTIMALITY OF ALLEN AND KENNEDY'S ALGORITHM FOR PARALLELISM EXTRACTION IN NESTED LOOPS
• Distributing and parallelizing non-canonical loops
• Compiler Algorithms for Synchronization
• The static parallelization of loops and recursions
• Fast Execution of Loops with IF Statements
• The semantics and complexity of parallel programs for vector computations. I: A case study using Ada
• scientific article; zbMATH DE number 1079700 (Why is no real title available?)

This page was built for publication: On the parallel complexity of loops

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