enthought / enthought/distarray

Sorting spitballing

未关闭
#321 1 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看
enhancement
主要语言
Python
星标
5
派生
1
PR 合并指标
30 天内没有已合并 PR

描述

Some sorting ideas for consideration:
- It is fairly reliable that communication overhead and latency are the dominant factors, so we want to minimize the total amount of communication.
- In general, sorting requires an all-to-all communication step: every worker has to send and receive data to and from every other worker, so there is potentially a lot of communication.
- We want to minimize the all-to-all communication as much as possible.
- We also assume that sorting the local array is efficient and a solved problem.
- If we can get all the right data to each worker, then sort the data locally with a local sort, then we're done. So the problem reduces to getting the right data to each worker.
- If we allow the sorted array to have an irregular block distribution that does not match the distribution of the original array, then that gives a lot of flexibility.

Assume we have `n` workers that share a block-distributed distarray. Assume we have some way to choose `n-1` pivots that partition the global array into `n` sections such that the number of elements in section `i` equals the number of elements on worker with rank `i`. Then the sort can proceed as follows:
- Partition each worker's localarray into `n` sections using the `n-1

贡献指南

这个仓库没有索引到贡献指南

调研方向

该 issue 没有列出任何文件、测试或入口点,并且在提案中途结束。首先审查完整的 issue,以及仓库中现有的分布式排序和数据分发工作。要视为完成,需要确定采用的方法、实现范围,以及测试或其他验证标准。

由索引模型根据 Issue 内容生成。

评估

技术栈
python
领域
distributed-systems
Issue 类型
功能
难度
5/5
预计耗时
一周以上
活跃度
停滞
描述清晰度
需要澄清
新手友好度
20/100

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。