Skip to content
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.

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

A new method for the greedy optimizer #41

Merged
merged 10 commits into from
May 30, 2024

Conversation

ArrogantGao
Copy link
Contributor

@ArrogantGao ArrogantGao commented May 28, 2024

The following changes have been made in this PR:

  1. Added a new optimizer "Hyper-Greedy". In each step, instead of directly selecting the contraction pair with the lowest cost, here we sampling one of them according to the cost $\exp(-L / t)$, where $L$ is the cost and $t$ is the temperature, thus it may given better results that greedy.
  2. Deps of BetterExp is removed, since it has been merge to Base since [email protected], and currently exp2 provided by Base seems better:
julia> @btime exp2(1.0);
  0.791 ns (0 allocations: 0 bytes)

julia> @btime BetterExp.exp2(1.0);
  1.625 ns (0 allocations: 0 bytes)

(betterexp) pkg> st
Status `~/temp/betterexp/Project.toml`
  [6e4b80f9] BenchmarkTools v1.5.0
  [7cffe744] BetterExp v0.1.0
  1. Added multi-threads support for tree_greedy.

Copy link
Member

@GiggleLiu GiggleLiu left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Add parameters alpha, move temperature to greedy.

Project.toml Show resolved Hide resolved
src/greedy.jl Outdated
@@ -5,7 +5,20 @@ end

struct MinSpaceOut end
struct MinSpaceDiff end
struct HyperGreedy{T}
t::T
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

temperature

src/greedy.jl Outdated Show resolved Hide resolved
@ArrogantGao
Copy link
Contributor Author

Added a new struct GreedyStrategy for method of GreedyMethod.
GreedyStrategy include parameters $\alpha$ and temperature, thus MinSpaceOut and MinSpaceDiff now are special case of GreedyStrategy.

Copy link
Member

@GiggleLiu GiggleLiu left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

GreedyStrategy seems to be not nessesary. We can move the fields to GreedyMethod.


MinSpaceOut() = GreedyStrategy(0.0, 0.0)
MinSpaceDiff() = GreedyStrategy(1.0, 0.0)


struct LegInfo{ET}
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

vi and vj not defined here. How about:

We use number 0, 1, 2 to denote the output tensor, the first input tensor and the second input tensor,
and use e.g. `l01` to denote the set of labels that appear in both the output tensor and the input tensor.

src/kahypar.jl Outdated
Comment on lines 102 to 107
# eincode = optimize_code(parse_eincode(incidence_list, tree, vertices=1:length(parts)), log2_sizes, sub_optimizer)
# if eincode isa SlicedEinsum
# @assert eincode.slicing == 0
# eincode = eincode.eins
# end
# tree = parse_tree(eincode, collect(1:length(parts)))
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
# eincode = optimize_code(parse_eincode(incidence_list, tree, vertices=1:length(parts)), log2_sizes, sub_optimizer)
# if eincode isa SlicedEinsum
# @assert eincode.slicing == 0
# eincode = eincode.eins
# end
# tree = parse_tree(eincode, collect(1:length(parts)))

src/kahypar.jl Outdated
@assert length(res.slicing) == 0
res = res.eins
end
# res = optimize_greedy(inset, iy1, size_dict; method=greedy_config.method, nrepeat=greedy_config.nrepeat)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
# res = optimize_greedy(inset, iy1, size_dict; method=greedy_config.method, nrepeat=greedy_config.nrepeat)

test/greedy.jl Outdated
Comment on lines 55 to 59
# eincode3 = ein"(ab,acd),bcef,e,df->"
# Random.seed!(2)
# optcode3 = optimize_greedy(eincode3, size_dict)
# tc, sc = timespace_complexity(optcode3, edge_sizes)
# @test 16 <= tc <= log2(exp2(10)+exp2(16)+exp2(15)+exp2(9)+1e-8)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
# eincode3 = ein"(ab,acd),bcef,e,df->"
# Random.seed!(2)
# optcode3 = optimize_greedy(eincode3, size_dict)
# tc, sc = timespace_complexity(optcode3, edge_sizes)
# @test 16 <= tc <= log2(exp2(10)+exp2(16)+exp2(15)+exp2(9)+1e-8)

@ArrogantGao
Copy link
Contributor Author

These commented parts have been removed, and the doc strings are revised.

@GiggleLiu GiggleLiu merged commit 3031953 into TensorBFS:master May 30, 2024
1 check passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants