[성능/아키텍처] FOriginBasedUE 공로 배정 수렴 지연 원인 분석 및 단계별 최적화 로드맵 #19

New Issue

DHH · 2026-03-20T14:24:28+09:00

DHH commented

2026-03-20 14:24:28 +09:00

1. 배경 및 분석 대상

솔루션: FOriginBasedUE/FOriginBasedUE.sln
진입점: FAssignment (OriginBasedUE_SingleClass.f90)
이슈: 대형 네트워크에서 수단별 다중요금(Multi-class/Multi-toll) 적용 시 경로/유량 상호작용이 복잡해지며 수렴 속도가 급격히 저하됨.

2. 핵심 병목 지점 및 지연 원인 (Technical Deep Dive)

내부 반복(Inner Loop) 부하: do k1 = 1, InnerIter(500) 루프 내에서 존(Zone) 수만큼 반복되는 SearchMinMaxPath + VolumeShift 연산이 전체 시간의 대부분을 점유.
고비용 수식 연산: VolumeShift 단계(PathBasedUE.f90)에서 유량 업데이트 시 pow(X, beta) 형태의 지수 연산이 반복적으로 발생하여 CPU 부하 가중.
Bush 재구성 오버헤드: 외부 반복마다 수행되는 4단계 사이클(BranchToBush → UpdateBush → OrderingWithCycle → BushToBranch)이 모든 존을 대상으로 수행되어 매 반복마다 상당한 비용 발생.
조기 수렴 실패 신호: 로그의 Freq=501은 내부 반복 상한(500회)을 모두 소진했음을 의미하며, 이는 현재의 파라미터나 구조로 수렴 지점에 도달하는 데 난항을 겪고 있음을 시사.

3. 최적화 로드맵 (Action Plan)

Phase 1: 결과 보존형(Equivalence) 최적화 (즉시 적용 가능)

배열 초기화 최적화: 매 존(Zone) 진입 시 전체 배열을 0으로 초기화하는 대신, 실제 변경된 인덱스만 관리하는 Touched Index 방식 도입.
OD 정렬 로직 개선: 입력 데이터(ReadData.f90:1123)가 이미 (oz, dz) 순으로 정렬되어 있다면 불필요한 재정렬 루프를 스킵하도록 조건부 로직 추가.
상수/계수 캐싱: DefineNetworkType 매핑 및 PCU/OCCUPANCY 계수 등 반복 계산되는 항목들을 사전 계산 테이블(Lookup Table)화하여 재사용.
로깅 I/O 병목 완화: 매 반복마다 발생하는 과도한 콘솔 출력 및 콜백 빈도를 수렴도에 따라 동적으로 조정.

Phase 2: 수렴 파라미터 및 알고리즘 조정 (검증 병행)

수렴 임계치 조정: 결과의 정밀도 차이를 모니터링하며 InnerIter, bRGap, bMaxShiftVolume, bTGap 파라미터를 점진적으로 완화.
특수 링크 처리 최적화: ExclusiveHOV(2) 등 턴 생성에서 제외되는 링크 타입에 대한 분기 처리를 조기에 수행하여 루프 계산량 감소.

4. 관련 소스 코드 위치

메인 루프: OriginBasedUE_SingleClass.f90:394-424
유량 업데이트: PathBasedUE.f90:1182-1210
데이터 로딩 및 상수 정의: ReadData.f90, VariableDefine.f90

**1. 배경 및 분석 대상** - **솔루션**: `FOriginBasedUE/FOriginBasedUE.sln` - **진입점**: `FAssignment` (`OriginBasedUE_SingleClass.f90`) - **이슈**: 대형 네트워크에서 **수단별 다중요금(Multi-class/Multi-toll)** 적용 시 경로/유량 상호작용이 복잡해지며 수렴 속도가 급격히 저하됨. **2. 핵심 병목 지점 및 지연 원인 (Technical Deep Dive)** - **내부 반복(Inner Loop) 부하**: `do k1 = 1, InnerIter(500)` 루프 내에서 존(Zone) 수만큼 반복되는 `SearchMinMaxPath` + `VolumeShift` 연산이 전체 시간의 대부분을 점유. - **고비용 수식 연산**: `VolumeShift` 단계(`PathBasedUE.f90`)에서 유량 업데이트 시 `pow(X, beta)` 형태의 지수 연산이 반복적으로 발생하여 CPU 부하 가중. - **Bush 재구성 오버헤드**: 외부 반복마다 수행되는 4단계 사이클(`BranchToBush` → `UpdateBush` → `OrderingWithCycle` → `BushToBranch`)이 모든 존을 대상으로 수행되어 매 반복마다 상당한 비용 발생. - **조기 수렴 실패 신호**: 로그의 `Freq=501`은 내부 반복 상한(500회)을 모두 소진했음을 의미하며, 이는 현재의 파라미터나 구조로 수렴 지점에 도달하는 데 난항을 겪고 있음을 시사. **3. 최적화 로드맵 (Action Plan)** **Phase 1: 결과 보존형(Equivalence) 최적화 (즉시 적용 가능)** - **배열 초기화 최적화**: 매 존(Zone) 진입 시 전체 배열을 0으로 초기화하는 대신, 실제 변경된 인덱스만 관리하는 **Touched Index** 방식 도입. - **OD 정렬 로직 개선**: 입력 데이터(`ReadData.f90:1123`)가 이미 `(oz, dz)` 순으로 정렬되어 있다면 불필요한 재정렬 루프를 스킵하도록 조건부 로직 추가. - **상수/계수 캐싱**: `DefineNetworkType` 매핑 및 `PCU/OCCUPANCY` 계수 등 반복 계산되는 항목들을 사전 계산 테이블(Lookup Table)화하여 재사용. - **로깅 I/O 병목 완화**: 매 반복마다 발생하는 과도한 콘솔 출력 및 콜백 빈도를 수렴도에 따라 동적으로 조정. **Phase 2: 수렴 파라미터 및 알고리즘 조정 (검증 병행)** - **수렴 임계치 조정**: 결과의 정밀도 차이를 모니터링하며 `InnerIter`, `bRGap`, `bMaxShiftVolume`, `bTGap` 파라미터를 점진적으로 완화. - **특수 링크 처리 최적화**: `ExclusiveHOV(2)` 등 턴 생성에서 제외되는 링크 타입에 대한 분기 처리를 조기에 수행하여 루프 계산량 감소. **4. 관련 소스 코드 위치** - 메인 루프: `OriginBasedUE_SingleClass.f90:394-424` - 유량 업데이트: `PathBasedUE.f90:1182-1210` - 데이터 로딩 및 상수 정의: `ReadData.f90`, `VariableDefine.f90`

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: DHH/issue-sample#19