비교 벤치마킹: 처리량이 많은 시나리오의 ILP, A*, 분기 및 바운드 알고리즘

이번 블로그 게시물에서는 최근 개인 프로젝트에 사용된 세 가지 알고리즘인 ILP(정수 선형 계획법) 알고리즘, A* 알고리즘을 활용한 로컬 알고리즘과 Branch and Bound 알고리즘을 활용한 최적화 솔루션입니다. 모든 알고리즘은 동일한 데이터 세트를 사용하여 테스트되었으며 ILP 및 Branch and Bound 구현은 동일한 워크로드를 공유했지만 A* 구현은 성능 제약으로 인해 제한되었습니다.

면책 조항: 프로젝트의 특정 코드 세부 사항을 자세히 다루지는 않지만, 이에 대한 몇 가지 통찰력을 공유하겠습니다. 코드베이스는 공개용이 아니며, 이는 코드의 기밀성을 존중한다는 면책 조항으로 사용됩니다.

벤치마크 결과

다음은 세 가지 알고리즘 모두에 대한 벤치마크 결과입니다.

goos: linux
goarch: amd64
pkg: github.com/sosalejandro/<my-project>/<my-package>/pkg
cpu: 13th Gen Intel(R) Core(TM) i7-13700HX

BenchmarkGenerateReportILP-24                            724       1694029 ns/op       30332 B/op        181 allocs/op
BenchmarkGenerateReportILPParallel-24                   6512        187871 ns/op       34545 B/op        184 allocs/op
BenchmarkGenerateReportLocal-24                            2     851314106 ns/op    559466456 B/op   7379756 allocs/op
BenchmarkBranchGenerateReportLocal-24                 101449         12106 ns/op       29932 B/op        165 allocs/op
BenchmarkGenerateReportLocalParallel-24                    3     349605952 ns/op    559422440 B/op   7379837 allocs/op
BenchmarkBranchGenerateReportLocalParallel-24         120543         10755 ns/op       29933 B/op        165 allocs/op
PASS
coverage: 81.4% of statements
ok      github.com/sosalejandro/<my-project>/<my-package>/pkg   11.121s
</my-package></my-project></my-package></my-project>

워크로드 구성

모든 알고리즘은 동일한 데이터 세트를 사용하여 테스트되었지만 작업량(즉, 각 항목이 처리되는 횟수)은 구현마다 달랐습니다.

ILP 및 분기 및 바인딩된 구현 작업 부하:

plan := []Plan{
    {ID: "1", Times: 100},
    {ID: "2", Times: 150},
    {ID: "3", Times: 200},
    {ID: "8", Times: 50},
    {ID: "9", Times: 75},
    {ID: "10", Times: 80},
    {ID: "11", Times: 90},
    {ID: "12", Times: 85},
    {ID: "13", Times: 60},
    {ID: "14", Times: 110},
}

A* 구현 작업량:

plan := []Plan{
    {ID: "1", Times: 1},
    {ID: "2", Times: 1},
    {ID: "3", Times: 5},
    {ID: "8", Times: 5},
    {ID: "9", Times: 5},
    {ID: "10", Times: 5},
    {ID: "11", Times: 9},
    {ID: "12", Times: 5},
    {ID: "13", Times: 5},
    {ID: "14", Times: 5},
}

워크로드 분석

이러한 워크로드가 벤치마크 결과에 미치는 영향을 이해하기 위해 각 구현에 대한 총 반복 횟수(즉, Times 값의 합)를 계산해 보겠습니다.

총 반복:

• ILP 및 분기 및 바인딩 구현:

  100 + 150 + 200 + 50 + 75 + 80 + 90 + 85 + 60 + 110 = 1000

• A* 구현:

  1 + 1 + 5 + 5 + 5 + 5 + 9 + 5 + 5 + 5 = 46

작업량 비율:

ILP Iterations / A* Iterations = 1000 / 46 ≈ 21.74

이는 ILP와 Branch and Bound 구현이 A* 구현에 비해 대략 21.74배 더 많은 반복을 처리한다는 의미입니다.

성능 비교

워크로드 차이에 따른 벤치마크 결과를 분석해 보겠습니다.

Benchmark	Runs	ns/op	B/op	allocs/op	Total Time (ns)
BenchmarkGenerateReportILP-24	724	1,694,029	30,332	181	≈ 1,225,836,996
BenchmarkGenerateReportILPParallel-24	6,512	187,871	34,545	184	≈ 1,223,607,552
BenchmarkBranchGenerateReportLocal-24	101,449	12,106	29,932	165	≈ 1,224,505,394
BenchmarkGenerateReportLocal-24	2	851,314,106	559,466,456	7,379,756	≈ 1,702,628,212
BenchmarkGenerateReportLocalParallel-24	3	349,605,952	559,422,440	7,379,837	≈ 1,048,817,856
BenchmarkBranchGenerateReportLocalParallel-24	120,543	10,755	29,933	165	≈ 1,295,219,065

관찰

1. 작업별 실행 시간:
   • BenchmarkGenerateReportILP-24 대 BenchmarkBranchGenerateReportLocal-24:
     • 분기 및 경계는 ILP보다 99.29% 더 빠르며 실행 시간을 1,694,029ns/op에서 12,106ns/op로 줄입니다. .

• BenchmarkGenerateReportILP-24 대 BenchmarkGenerateReportLocal-24:

  • ILP는 로컬보다 99.80% 더 빠르며 실행 시간을 851,314,106ns/op에서 1,694,029ns/op.

• BenchmarkGenerateReportILPParallel-24 대 BenchmarkBranchGenerateReportLocalParallel-24:

  • 분기 및 바운드 병렬은 ILP 병렬보다 94.28% 더 빠르며 실행 시간을 187,871ns/op에서 10,755ns로 줄입니다. /op.

• BenchmarkGenerateReportILPParallel-24 대 BenchmarkGenerateReportLocalParallel-24:

  • ILP 병렬은 로컬 병렬보다 99.95% 더 빠르며 실행 시간을 349,605,952ns/op에서 187,871ns/op로 줄입니다. .

1. 메모리 할당:

   • ILP 구현: 병렬 실행 시 메모리 사용량 및 할당이 약간 증가합니다.
   • 분기 및 바운드 구현: A* 구현에 비해 메모리 사용량 및 할당이 적습니다.
   • A* 구현: 메모리 할당이 매우 높아 리소스 활용도가 비효율적입니다.

2. 처리량:

   • ILP 병렬 및 분기 및 경계 병렬은 작업량이 많아 약 21.74배 더 많은 반복을 처리할 수 있습니다.
   • A* 구현 처리량 문제는 반복 횟수가 현저히 적기 때문이 아니라 비효율적인 메모리 사용 및 구현 때문입니다.

다양한 작업 부하가 성능에 미치는 영향

ILP 및 Branch 알고리즘이 테스트 반복당

21.74배 더 많은 처리량을 처리한다는 점을 고려하면 이러한 워크로드 차이는 각 알고리즘의 성능과 효율성에 영향을 미칩니다.

• ILP 및 분기 알고리즘: 더 많은 처리량을 처리하므로 더 높은 워크로드에 최적화되어 있습니다. 더 많은 작업을 처리함에도 불구하고 더 빠른 실행 시간을 유지합니다. 이는 계산적으로 효율적일 뿐만 아니라 처리량이 많은 시나리오에도 적합하다는 것을 의미합니다.

• 로컬 알고리즘: 처리량이 적고 실행 시간이 길기 때문에 이 알고리즘은 증가된 작업 부하를 처리하는 데 효율성이 떨어집니다. ILP 또는 Branch와 동일한 처리량으로 확장하면 실행 시간이 크게 늘어나 처리량이 많은 경우에는 적합하지 않음을 나타냅니다.

워크로드가 증가하는 시나리오에서는 더 높은 처리량을 효율적으로 관리할 수 있는 능력으로 인해 ILP와 Branch가 로컬보다 성능이 뛰어납니다. 반대로, 워크로드가 줄어들면 로컬 알고리즘은 ILP 및 Branch에 더 가까운 성능을 발휘할 수 있지만 알고리즘 효율성의 근본적인 차이로 인해 여전히 지연될 가능성이 있습니다.

알고리즘 개요

각 알고리즘이 문제 해결에 어떻게 접근하는지 더 명확하게 이해할 수 있도록 해당 메커니즘과 방법론에 대한 일반적인 개요를 소개합니다.

정수 선형 계획법(ILP)

목적:

ILP는 요구사항이 선형 관계로 표현되는 수학적 모델에서 최상의 결과(예: 최대 이익 또는 최저 비용)를 찾는 데 사용되는 최적화 기술입니다. 선형 제약 조건과 선형 목적 함수로 표현 가능한 문제에 특히 효과적입니다.

일반 작업 흐름:

1. 변수 정의:
   
   선택을 나타내는 의사결정 변수를 식별합니다.

2. 목적함수:
   
   최대화하거나 최소화해야 하는 선형 방정식을 공식화합니다.

3. 제약조건:
   
   솔루션이 충족해야 하는 선형 부등식 또는 등식을 설정합니다.

4. 해결 방법:
   
   ILP 솔버를 활용하여 모든 제약조건을 만족하면서 목적함수를 최대화 또는 최소화하는 의사결정변수의 최적값을 찾습니다.

의사 코드:

goos: linux
goarch: amd64
pkg: github.com/sosalejandro/<my-project>/<my-package>/pkg
cpu: 13th Gen Intel(R) Core(TM) i7-13700HX

BenchmarkGenerateReportILP-24                            724       1694029 ns/op       30332 B/op        181 allocs/op
BenchmarkGenerateReportILPParallel-24                   6512        187871 ns/op       34545 B/op        184 allocs/op
BenchmarkGenerateReportLocal-24                            2     851314106 ns/op    559466456 B/op   7379756 allocs/op
BenchmarkBranchGenerateReportLocal-24                 101449         12106 ns/op       29932 B/op        165 allocs/op
BenchmarkGenerateReportLocalParallel-24                    3     349605952 ns/op    559422440 B/op   7379837 allocs/op
BenchmarkBranchGenerateReportLocalParallel-24         120543         10755 ns/op       29933 B/op        165 allocs/op
PASS
coverage: 81.4% of statements
ok      github.com/sosalejandro/<my-project>/<my-package>/pkg   11.121s
</my-package></my-project></my-package></my-project>

A* 알고리즘(로컬 구현)

목적:

A*는 성능과 정확성으로 잘 알려진 길 찾기 및 그래프 탐색 알고리즘입니다. 균등 비용 검색과 순수 휴리스틱 검색 기능을 결합하여 노드 간 최단 경로를 효율적으로 찾아냅니다.

일반 작업 흐름:

1. 초기화:
   
   초기 노드로 시작하여 우선순위 대기열에 추가합니다.

2. 루프:

   • 우선순위 대기열에서 예상 비용이 가장 낮은 노드를 제거합니다.
   • 목표 노드라면 종료하세요.
   • 그렇지 않으면 이웃을 탐색하여 노드를 확장하세요.
   • 각 이웃에 대해 새로운 비용을 계산하고 그에 따라 우선순위 대기열을 업데이트합니다.

3. 해지:
   
   목표 노드에 도달하거나 우선순위 큐가 비어 있으면(경로가 없음을 나타냄) 알고리즘이 종료됩니다.

의사 코드:

goos: linux
goarch: amd64
pkg: github.com/sosalejandro/<my-project>/<my-package>/pkg
cpu: 13th Gen Intel(R) Core(TM) i7-13700HX

BenchmarkGenerateReportILP-24                            724       1694029 ns/op       30332 B/op        181 allocs/op
BenchmarkGenerateReportILPParallel-24                   6512        187871 ns/op       34545 B/op        184 allocs/op
BenchmarkGenerateReportLocal-24                            2     851314106 ns/op    559466456 B/op   7379756 allocs/op
BenchmarkBranchGenerateReportLocal-24                 101449         12106 ns/op       29932 B/op        165 allocs/op
BenchmarkGenerateReportLocalParallel-24                    3     349605952 ns/op    559422440 B/op   7379837 allocs/op
BenchmarkBranchGenerateReportLocalParallel-24         120543         10755 ns/op       29933 B/op        165 allocs/op
PASS
coverage: 81.4% of statements
ok      github.com/sosalejandro/<my-project>/<my-package>/pkg   11.121s
</my-package></my-project></my-package></my-project>

분기 및 바운드 알고리즘

목적:

Branch and Bound는 솔루션 공간을 체계적으로 탐색하는 최적화 알고리즘입니다. 문제를 더 작은 하위 문제로 나누고(분기) 경계를 사용하여 현재 최선의 문제(경계)보다 더 나은 솔루션을 생성할 수 없는 하위 문제를 제거합니다.

일반 작업 흐름:

1. 초기화:
   
   초기 솔루션부터 시작하여 가장 잘 알려진 솔루션을 설정하세요.

2. 분기:
   
   각 노드에서 문제를 더 작은 하위 문제로 나눕니다.

3. 경계:
   
   각 분기에서 가능한 최상의 솔루션에 대한 낙관적 추정치(상한)를 계산합니다.

4. 가지치기:
   
   상한이 가장 잘 알려진 솔루션보다 나쁜 분기는 삭제하세요.

5. 검색:
   
   깊이 우선 또는 최고 우선 검색을 사용하여 나머지 분기를 재귀적으로 탐색합니다.

6. 해지:
   
   모든 가지를 정리하거나 탐색한 경우 가장 잘 알려진 솔루션이 최적입니다.

의사 코드:

goos: linux
goarch: amd64
pkg: github.com/sosalejandro/<my-project>/<my-package>/pkg
cpu: 13th Gen Intel(R) Core(TM) i7-13700HX

BenchmarkGenerateReportILP-24                            724       1694029 ns/op       30332 B/op        181 allocs/op
BenchmarkGenerateReportILPParallel-24                   6512        187871 ns/op       34545 B/op        184 allocs/op
BenchmarkGenerateReportLocal-24                            2     851314106 ns/op    559466456 B/op   7379756 allocs/op
BenchmarkBranchGenerateReportLocal-24                 101449         12106 ns/op       29932 B/op        165 allocs/op
BenchmarkGenerateReportLocalParallel-24                    3     349605952 ns/op    559422440 B/op   7379837 allocs/op
BenchmarkBranchGenerateReportLocalParallel-24         120543         10755 ns/op       29933 B/op        165 allocs/op
PASS
coverage: 81.4% of statements
ok      github.com/sosalejandro/<my-project>/<my-package>/pkg   11.121s
</my-package></my-project></my-package></my-project>

비교 분석

Feature	ILP Implementation	Local (A*) Implementation	Branch and Bound Implementation
Optimization Approach	Formulates the problem as a set of linear equations and inequalities to find the optimal solution.	Searches through possible states using heuristics to find the most promising path to the goal.	Systematically explores and prunes the solution space to find optimal solutions efficiently.
Scalability	Handles large-scale problems efficiently by leveraging optimized solvers.	Performance can degrade with increasing problem size due to the exhaustive nature of state exploration.	Efficient for combinatorial problems, with pruning reducing the search space significantly.
Development Time	Faster implementation as it relies on existing ILP solvers and libraries.	Requires more time to implement, especially when dealing with complex state management and heuristics.	Moderate development time, balancing complexity and optimization benefits.
Flexibility	Highly adaptable to various linear optimization problems with clear constraints and objectives.	Best suited for problems where pathfinding to a goal is essential, with heuristic guidance.	Effective for a wide range of optimization problems, especially combinatorial ones.
Performance	Demonstrates superior performance in handling a higher number of iterations with optimized memory usage.	While effective for certain scenarios, struggles with high memory allocations and longer execution times under heavy workloads.	Shows significant performance improvements over ILP and A* with optimized memory usage and faster execution times.
Developer Experience	Improves developer experience by reducing the need for extensive coding and optimization efforts.	May require significant debugging and optimization to achieve comparable performance levels.	Balances performance with manageable development effort, leveraging existing strategies for optimization.
Integration	Currently integrates a C ILP module with Golang, facilitating efficient computation despite cross-language usage.	Fully implemented within Golang, but may face limitations in performance and scalability without optimizations.	Implemented in Golang, avoiding cross-language integration complexities and enhancing performance.

서버 성능에 미치는 영향

• 확장성:

  • 분기 및 바운드 구현은 뛰어난 확장성을 보여주며 대기 시간을 줄이면서 많은 수의 동시 요청을 효율적으로 처리합니다.
  • ILP 병렬 구현 역시 뛰어난 확장성을 보여주며 대기 시간을 줄이면서 많은 수의 동시 요청을 효율적으로 처리합니다.
  • A* 구현은 성능 제한으로 인해 고부하 환경에 적합하지 않습니다.

• 자원 활용도:

  • 분기 및 바운드 구현 낮은 메모리 소비와 빠른 실행 시간으로 리소스를 효율적으로 활용합니다.
  • ILP 병렬은 멀티 코어 CPU를 효과적으로 활용하여 관리 가능한 메모리 소비로 높은 처리량을 제공합니다.
  • A* 구현은 과도한 메모리를 소비하여 잠재적으로 리소스 고갈을 초래할 수 있습니다.

워크로드가 성능에 미치는 영향

워크로드 차이는 알고리즘 성능에 영향을 미칩니다.

• 분기 및 바인딩 구현은 ILP 구현과 동일한 작업 부하를 효율적으로 처리하여 빠른 실행 시간과 낮은 메모리 사용량을 제공하므로 확장에 적합합니다.

• ILP 구현은 최적화된 솔버로 인해 더 큰 작업 부하를 효율적으로 처리합니다.

• A* 구현은 높은 실행 시간과 메모리 사용량으로 인해 성능에 어려움을 겪습니다.

결론

Branch and Bound 알고리즘을 사용하여 최적화된 솔루션을 사용하여 추가 비교를 추가했는데, 이는 성능 및 리소스 활용 측면에서 ILP 및 A* 알고리즘에 비해 얼마나 크게 향상되었는지 보여줍니다. Branch and Bound 알고리즘에 사용되는 작업량은 ILP 알고리즘과 동일합니다.

Branch and Bound 기반 BenchmarkBranchGenerateReportLocalParallel 기능은 탁월한 성능 향상을 보여 높은 동시성과 효율적인 리소스 관리가 요구되는 서버 환경에 매우 적합합니다.

분기 및 경계 접근 방식의 장점을 활용하고 이를 특정 문제에 맞게 최적화하는 데 중점을 두어 프로젝트의 성능과 확장성을 유지하고 증가하는 수요를 쉽게 처리할 수 있도록 할 수 있습니다.

최종 생각

강력한 애플리케이션을 구축하려면 성능, 확장성, 개발자 경험의 균형을 맞추는 것이 중요합니다. 분기 및 바운드 접근 방식은 현재 설정에서 가장 효율적인 것으로 입증되었으며 합리적인 개발 노력으로 상당한 성능 향상을 제공합니다.

각 알고리즘 접근 방식의 장점을 지속적으로 프로파일링하고 최적화하고 활용함으로써 고성능의 확장 가능하며 개발자 친화적인 시스템을 유지할 수 있습니다.

위 내용은 비교 벤치마킹: 처리량이 많은 시나리오의 ILP, A*, 분기 및 바운드 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!