Scholarlink

We present a deterministic parallel external-memory (PEM) algorithm that sorts N integers from \(\{1,2,\dots ,l\}\) . The algorithm sorts N integers from [1, l] in \( O\left( \frac{\log l}{\log m} \left( \frac{M}{B} + \log _{M/B} \frac{N}{B} \right) \right) \) parallel steps and \( O\left( \frac{N}{B} \cdot \frac{\log l}{\log (M/B)} \right) \) I/O operations. on the Concurrent Read Exclusive Write PEM model. (Here M is the size of the internal main memory of processors and B is the block size for I/Os.)

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Deterministic Integer Sorting on the Parallel External Memory Model

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Ranajit Senko,
  • G. Sajith

摘要

We present a deterministic parallel external-memory (PEM) algorithm that sorts N integers from \(\{1,2,\dots ,l\}\) . The algorithm sorts N integers from [1, l] in \( O\left( \frac{\log l}{\log m} \left( \frac{M}{B} + \log _{M/B} \frac{N}{B} \right) \right) \) parallel steps and \( O\left( \frac{N}{B} \cdot \frac{\log l}{\log (M/B)} \right) \) I/O operations. on the Concurrent Read Exclusive Write PEM model. (Here M is the size of the internal main memory of processors and B is the block size for I/Os.)