Skip to content

Graph Partitioning #2298

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
beicy opened this issue Jan 24, 2019 · 0 comments
Open

Graph Partitioning #2298

beicy opened this issue Jan 24, 2019 · 0 comments
Assignees
@beicy

Comments

@beicy
Copy link
Contributor

beicy commented Jan 24, 2019 •
edited
Loading

This issue is created to track Graph Partitioning work. It is also related to #2045.
Current Plan:

  1. Get the initial partitions based on BFS order. Each partition should satisfy device memory constraints.
  2. By adjusting the initial partitions (e.g. Kernighan–Lin algorithm), find out the optimized partitions based on proposed cost model ( Communication cost, computation cost, and workload balance).

Error Handling:
If there is one node who requires memory exceeds the given available memory, Partitioner will report an error.

Related issue #2687
@beicy beicy mentioned this issue Jan 24, 2019
Merged
@beicy beicy self-assigned this Jan 24, 2019
@beicy beicy mentioned this issue Jan 25, 2019
Merged
This was referenced Feb 6, 2019
Merged
Merged
@nrsatish nrsatish mentioned this issue Mar 5, 2019
Merged
@beicy beicy mentioned this issue Mar 14, 2019
Merged
@beicy beicy mentioned this issue May 30, 2019
Closed
@beicy beicy mentioned this issue Jun 7, 2019
Closed
facebook-github-bot pushed a commit that referenced this issue Jun 19, 2019
@facebook-github-bot
refactoring the way to calculate the memory usage of a node set (#3062)
038b8b0 
Summary:
Refactoring the way to calculate the memory usage of a node set -- update the memory usage by adding node to the nodes set one by one.
Will polish the the usage in following PR.

Documentation:
#2298
[Optional Fixes #issue]
Pull Request resolved: #3062

Test Plan:
Added unnitest.

Please see a detailed explanation of how to fill out the fields in the relevant sections in PULL_REQUEST.md.

Differential Revision: D15884632

Pulled By: beicy

fbshipit-source-id: 82b434518632d0b5286fc452c08c183fa3f0be5c
@beicy beicy mentioned this issue Jul 16, 2019
Closed
facebook-github-bot pushed a commit that referenced this issue Jul 18, 2019
@facebook-github-bot
User-defined partition (#3237)
809a3e8 
Summary:
This PR added user-defined partition flow. Basically, a struct "PartitionConfig" containing the partition info is passed into Partitioner to enable this flow.  Now we let users have the full control of how to do the partitioning.
To use this flow, users can write their helper function to generate  PartitionConfig, and call Partitioner directly.
In the following PR, we will add passing PartitionConfig through HostManager from a yaml file.

Related to #2298
Documentation:

[Optional Fixes #issue]
Pull Request resolved: #3237

Test Plan:
Added unittest. ninja test.

Please see a detailed explanation of how to fill out the fields in the relevant sections in PULL_REQUEST.md.

Differential Revision: D16345755

Pulled By: beicy

fbshipit-source-id: 64f601004880e1702f5f6eba19d4f5b7749f0864
@beicy beicy mentioned this issue Jul 24, 2019
Closed
facebook-github-bot pushed a commit that referenced this issue Jul 26, 2019
@facebook-github-bot
Partitioner Refactoring -part1 (#3293)
e19970f 
Summary:
This PR is the first step of Partitioner refactoring:
1) Move the types used in Partitioner from Partitioner.h to PartitionerTypes.h
2) Move the partition optimizations from Partitioner class to a separate file PartitionerOptimization.cpp
3) Move the partition validation from Partitioner class to a separate file PartitionerValidation.cpp.

Documentation:

[Optional Fixes #issue]
#2298
Pull Request resolved: #3293

Test Plan:
current test.
Please see a detailed explanation of how to fill out the fields in the relevant sections in PULL_REQUEST.md.

Reviewed By: bertmaher

Differential Revision: D16465488

Pulled By: beicy

fbshipit-source-id: e464481df20d2a171b51e82da5eaaf0c2bb0661d
@beicy beicy mentioned this issue Jul 29, 2019
Closed
facebook-github-bot pushed a commit that referenced this issue Jul 30, 2019
@facebook-github-bot
Partitioner Refactoring 2 (#3318)
bbb1b84 
Summary:
In this PR, the following methods are updated ( the way of how to calculate the memory usage/computation for each node is not changed)  :
1. In previous version, Partitioner had a map to store the node and its memory usage.  Now this one is removed, and a function `uint64_t getNodeMemUsage(const Node *node) ` is added in to PartitionerUtils.cpp. That is, instead of pre-calculating all nodes' memory usage and storing it in a map, we calculate it when it is necessary.  This function is now only called in `loadBalancedPartitioning`, and for each node, it is only called once. So no need to store the value in a map.
 2. In previous version, Partitioner had a map to store the node and its computation time. Similar as the above memory usage refactoring,  a function `float getNodeComputeTime(const Node *node, const BackendInfo backendInfo)` is added to return the computation time of a node when it is necessary.  Now the backendInfo is added as a param in this function for different type of backends.

Documentation:
#2298
[Optional Fixes #issue]
Pull Request resolved: #3318

Test Plan:
ninja test.

Please see a detailed explanation of how to fill out the fields in the relevant sections in PULL_REQUEST.md.

Reviewed By: gcatron, nickgg

Differential Revision: D16558869

Pulled By: beicy

fbshipit-source-id: 69111ba02f041a85dd230319fb2e68516c4db87d
@beicy beicy mentioned this issue Aug 5, 2019
Closed
facebook-github-bot pushed a commit that referenced this issue Aug 12, 2019
@facebook-github-bot
Partitioner refactoring 3 (#3384)
3706588 
Summary:
In this PR:
1. Added `class ParititionerBase` which contains interfaces and common functions used for partitioner.  and the `class Partitioner` is now derived from `class ParititionerBase` .
2. In `class Partitioner`, we have 3 partition approaches:
```
llvm::Error HeterogeneousPartition(CompilationContext &cctx);
llvm::Error QuantizationProfilingPartition(CompilationContext &cctx);
llvm::Error PartitionFromConfig(PartitionConfig &partitionConfig);
````
The above 3 method can be called directly by users, or chosen by
`llvm::Error Partition(CompilationContext &cctx)`

Note:  `loadBalancedPartitioning` is still included in `HeterogeneousPartition` since it uses the result of current partitioner approach. Will take it from `HeterogeneousPartition` in next PR and make it as the 4th partition approach.

Documentation:

[Optional Fixes #issue]
#2298
Pull Request resolved: #3384

Test Plan:
Ninja test, ./tests/image/run.sh
Please see a detailed explanation of how to fill out the fields in the relevant sections in PULL_REQUEST.md.

Differential Revision: D16685598

Pulled By: beicy

fbshipit-source-id: 91f3725b928f7376a9aef12fd1d1d65471506f6b
@beicy beicy mentioned this issue Aug 12, 2019
Closed
facebook-github-bot pushed a commit that referenced this issue Aug 14, 2019
@facebook-github-bot
Partitioner refactoring - final (#3409)
ae4114f 
Summary:
This is the last main parts of Partitioner refactoring:
1) Rewrote the load-balanced partition as a separate partition flow instead of an optimization pass since this one only uses the number of partitions generated by auto partition and overwrites the partition results.
2) Added unittest for load-balanced partition.
3) Abstract some common code as functions.

Documentation:

[Optional Fixes #issue]
#2298
Pull Request resolved: #3409

Test Plan:
added unnitest, ninja test, ./tests/images/run.sh

Please see a detailed explanation of how to fill out the fields in the relevant sections in PULL_REQUEST.md.

Differential Revision: D16791977

Pulled By: beicy

fbshipit-source-id: 2a3042764820c1dfc64d47352629704682fcb058
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@beicy beicy

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@beicy