초록 |
알고리즘의 고유 데이터 전송률에 대한 양자화 방법이 제공된다. 알고리즘의 고유 데이터 전송률에 대한 양자화 방법은 고유 데이터 전송률은 제1 오퍼레이터에 의하여 측정되고 그리고 제1 자료를 제2 오퍼레이터로부터 다른 오퍼레이터로 전송하는 것에 관련되며, 다양한 데이터 단위입자들에서 상기 고유 데이터 전송률에 대한 양자화 방법에 있어서, 상기 제1 자료가 상기 제2 오퍼레이터에 의하여 사용되었는지를 검출하는 단계; 각 정점들은 동작(operation) 및 자료 중 하나를 나타내며, 각 에지들은 데이터 전송을 나타내고, vi 는 i번째 정점이며, 상기 검출된 제1 자료가 상기 제2 오퍼레이터에 의하여 전에 사용되지 않고, 상기 제2 오퍼레이터에 의하여 미래에 사용되지 않을 경우, 상기 제1 오퍼레이터에 의하여 n 정점들 및 m 에지들 그리고 ij 요소들 L(i,j)을 갖는 라플라시안 행렬 L 을 포함하는 파인-그레인드(fine-grained) 데이터 흐름 그래프 G를 제공하는 단계; n 개의 요소들은 상기 데이터 흐름 그래프 G의 상기 n 정점들과 관련된 n변수들이고, vi 가 vj 에 인접할 때 는 모든 동작(operation) 쌍들을 나타내며, 그것의 각각은 적어도 2개의 인접한 상기 정점들을 포함하고, 상기 n 정점들이 서브 그래프들로 분리될 때, 제1 오퍼레이터에 의하여 상기 m 에지들 내에서 에지 컷(edge cut)들의 총 수의 최대값을 계산하기 위한 와 같은 n 요소들을 가진 벡터 x를 제공하는 단계; 파인-그레인드 데이터 단위입자에서 상기 고유 데이터 전송률의 최대량을 추정하기 위하여 상기 제1 오퍼레이터에 의하여 상기 최대값을 이용하는 단계; 상기 파인-그레인드 데이터 흐름 그래프 G를 캡슐화함(encapsulating)에 의해 코스-그레인드(coarse-grained) 데이터 흐름 그래프 G'를 구축하고, 그리고 나서 상기 코스-그레인드 데이터 흐름 그래프 G'에 대응하는 라플라시안 행렬 L'과 함께 코스-그레인드 데이터 단위입자에서 상기 고유 데이터 전송률을 양자화하는 단계; 그리고 상기 다양한 데이터 단위입자들의 양자화된 결과들로부터 평균 및 순간 데이터 전송률을 얻는 단계를 포함한다. |