| 1 |
1
분산 컴퓨팅의 매개변수를 업데이트하기 위한 경사 하강 계산 태스크를 게시하고, 게시된 태스크를 복수의 엔드 디바이스로 전송하여 복수의 엔드 디바이스로부터 관련 정보를 입력 받아 복수의 엔드 디바이스를 그룹화하며, 그룹화된 각 클러스터의 스트래글러(straggler) 수를 결정하여 결정된 스트래글러 수를 경사 하강 계산을 위한 인코딩 체계와 함께 복수의 엔드 디바이스로 전송하고, 복수의 엔드 디바이스에 대해 인코딩 결과에 따른 인센티브를 분배하는 파라미터 서버(Parameter Server; PS); 파라미터 서버로부터 게시된 태스크를 수신하고, 게시된 태스크에 대한 참여의사 및 관련 정보를 파라미터 서버로 전송한 후, 파라미터 서버로부터 복수의 엔드 디바이스의 그룹화 및 관련 정보를 입력 받아 CPU 사이클 주파수를 결정하고, 경사 하강 계산을 위한 인코딩을 수행하여 계산된 경사도를 파라미터 서버로 전송하는 복수의 엔드 디바이스(End Device; ED); 복수의 엔드 디바이스와 파라미터 서버가 통신하도록 무선 통신을 통해 복수의 엔드 디바이스와 통신하고, 유선 링크를 통해 파라미터 서버와 통신하는 기지국(Base Station); 및 복수의 엔드 디바이스와 파라미터 서버에서 처리된 데이터가 저장되고, 복수의 엔드 디바이스 각각에 대한 로컬 데이터 저장부를 포함하는 데이터 저장부(Data Shard; DS) 를 포함하는 코딩 및 인센티브 기반 분산 컴퓨팅 관리 시스템
|
| 2 |
2
제1항에 있어서,상기 복수의 엔드 디바이스는, 파라미터 서버와의 경쟁을 슈타켈버그 게임(Stackelberg game)으로 공식화하고, 슈타켈버그 게임의 리더로서 동작하는 복수의 엔드 디바이스는 각각의 엔드 디바이스의 컴퓨팅 속도와 에너지 소비량의 균형을 맞춰 인센티브 메커니즘과 최대 효용성을 얻기 위한 CPU 사이클 주파수를 결정하는 코딩 및 인센티브 기반 분산 컴퓨팅 관리 시스템
|
| 3 |
3
제2항에 있어서,상기 파라미터 서버는, 분산 컴퓨팅의 지연 시간을 최소화하는 것을 목표로 하고, 슈타켈버그 게임의 팔로워로서 동작하여 복수의 엔드 디바이스를 통해 결정된 CPU 사이클 주파수에 따라 각각의 엔드 디바이스에 대한 로드 할당을 결정한 후, 슈타켈버그 게임의 고유 내쉬 균형(Unique Nash equilibrium)인 슈타켈버그 균형을 달성하는 코딩 및 인센티브 기반 분산 컴퓨팅 관리 시스템
|
| 4 |
4
제1항에 있어서,상기 복수의 엔드 디바이스는, 파라미터 서버로부터 인센티브를 획득하기 위해 복수의 엔드 디바이스 간의 이익 극대화(Profit Maximization; PM) 서브게임을 형성하여 서로 경쟁하고, 상기 파라미터 서버는, 이익 극대화 서브게임에서 결정된 엔드 디바이스의 최상의 응답에 대하여 단일 팔로워로서 태스크 완료 지연 시간을 최소화하기 위한 로드를 해당 엔드 디바이스에 할당하는코딩 및 인센티브 기반 분산 컴퓨팅 관리 시스템
|
| 5 |
5
제4항에 있어서,상기 파라미터 서버는, 태스크 완료 지연 시간을 최소화하기 위해 그룹화된 각 클러스터에 대한 최적의 스트래글러의 수를 결정하고, 최적의 스트래글러 수에 따른 로드 할당을 결정하며, 최적의 스트래글러의 수를 결정하기 위해 라그랑지(Lagrange) 이중 문제를 재구성하고, 라그랑지 이중 문제를 최대화하는 최적의 라그랑지안 승수 벡터를 이용하여 최적의 스트래글러의 수를 결정하는 코딩 및 인센티브 기반 분산 컴퓨팅 관리 시스템
|
| 6 |
6
제1항에 있어서,상기 파라미터 서버는, 기본 인센티브 분배 및 경쟁 인센티브 분배를 포함하는 인센티브 분배 방식을 이용하여, 복수의 엔드 디바이스에 대한 최소 인센티브를 보장하는 기본 인센티브를 제공함으로써 복수의 엔드 디바이스의 참여를 유도하고, 모든 복수의 엔드 디바이스로부터 평가 결과를 입력 받으면, 평가 결과에 따른 인센티브를 제공하는 경쟁 인센티브를 복수의 엔드 디바이스에 분배하는코딩 및 인센티브 기반 분산 컴퓨팅 관리 시스템
|
| 7 |
7
제6항에 있어서,상기 복수의 엔드 디바이스는, 복수의 엔드 디바이스의 이익이 미리 결정된 최소값 이하로 되는 것을 방지하기 위해 모든 참여 엔드 디바이스에게 균등하게 분배되는 기본 인센티브를 분배 받는 코딩 및 인센티브 기반 분산 컴퓨팅 관리 시스템
|
| 8 |
8
제6항에 있어서,상기 복수의 엔드 디바이스는, 인센티브에 대한 복수의 엔드 디바이스 간 경쟁을 통해 복수의 엔드 디바이스가 처리한 태스크의 평가 결과에 비례하여 경쟁 인센티브를 분배 받고, 평가 결과는 워크로드(Workload; WL) 및 완료 시간(Completion Time; CT)을 포함하는 평가 기준에 따라 평가되며, 워크로드 기반 경쟁 인센티브는 엔드 디바이스가 처리한 워크로드의 양으로 평가되고, 완료 시간 기반 경쟁 인센티브는 엔드 디바이스의 예상 태스크 완료 지연 시간으로 평가되는 코딩 및 인센티브 기반 분산 컴퓨팅 관리 시스템
|
| 9 |
9
파라미터 서버(Parameter Server; PS)가 분산 컴퓨팅의 매개변수를 업데이트하기 위한 경사 하강 계산 태스크를 게시하고, 게시된 태스크를 복수의 엔드 디바이스로 전송하는 단계; 복수의 엔드 디바이스(End Device; ED)가 파라미터 서버로부터 게시된 태스크를 수신하고, 게시된 태스크에 대한 참여의사 및 관련 정보를 파라미터 서버로 전송하는 단계; 파라미터 서버가 복수의 엔드 디바이스로부터 참여의사 및 관련 정보를 입력 받아 복수의 엔드 디바이스를 그룹화하는 단계; 복수의 엔드 디바이스가 파라미터 서버로부터 복수의 엔드 디바이스의 그룹화 및 관련 정보를 입력 받아 CPU 사이클 주파수를 결정하는 단계; 파라미터 서버가 결정된 CPU 사이클 주파수에 따라 그룹화된 각 클러스터의 스트래글러(straggler) 수를 결정하고, 결정된 스트래글러 수를 경사 하강 계산을 위한 인코딩 체계와 함께 복수의 엔드 디바이스로 전송하는 단계; 복수의 엔드 디바이스가 경사 하강 계산을 위한 인코딩을 수행하여 계산된 경사도를 파라미터 서버로 전송하는 단계; 및 파라미터 서버가 복수의 엔드 디바이스에 대해 인코딩 결과에 따른 인센티브를 분배하는 단계를 포함하는 코딩 및 인센티브 기반 분산 컴퓨팅 관리 방법
|
| 10 |
10
제9항에 있어서, 상기 복수의 엔드 디바이스가 파라미터 서버로부터 복수의 엔드 디바이스의 그룹화 및 관련 정보를 입력 받아 CPU 사이클 주파수를 결정하는 단계는, 파라미터 서버와의 경쟁을 슈타켈버그 게임(Stackelberg game)으로 공식화하고, 슈타켈버그 게임의 리더로서 동작하는 복수의 엔드 디바이스는 각각의 엔드 디바이스의 컴퓨팅 속도와 에너지 소비량의 균형을 맞춰 인센티브 메커니즘과 최대 효용성을 얻기 위한 CPU 사이클 주파수를 결정하는 코딩 및 인센티브 기반 분산 컴퓨팅 관리 방법
|
| 11 |
11
제10항에 있어서, 상기 파라미터 서버가 결정된 CPU 사이클 주파수에 따라 그룹화된 각 클러스터의 스트래글러(straggler) 수를 결정하고, 결정된 스트래글러 수를 경사 하강 계산을 위한 인코딩 체계와 함께 복수의 엔드 디바이스로 전송하는 단계는, 상기 파라미터 서버가 분산 컴퓨팅의 지연 시간을 최소화하는 것을 목표로 하고, 슈타켈버그 게임의 팔로워로서 동작하여 복수의 엔드 디바이스를 통해 결정된 CPU 사이클 주파수에 따라 각각의 엔드 디바이스에 대한 로드 할당을 결정한 후, 슈타켈버그 게임의 고유 내쉬 균형(Unique Nash equilibrium)인 슈타켈버그 균형을 달성하는 코딩 및 인센티브 기반 분산 컴퓨팅 관리 방법
|
| 12 |
12
제11항에 있어서, 태스크 완료 지연 시간을 최소화하기 위해 그룹화된 각 클러스터에 대한 최적의 스트래글러의 수를 결정하고, 최적의 스트래글러 수에 따른 로드 할당을 결정하며, 최적의 스트래글러의 수를 결정하기 위해 라그랑지(Lagrange) 이중 문제를 재구성하고, 라그랑지 이중 문제를 최대화하는 최적의 라그랑지안 승수 벡터를 이용하여 최적의 스트래글러의 수를 결정하는 코딩 및 인센티브 기반 분산 컴퓨팅 관리 방법
|
| 13 |
13
제9항에 있어서, 상기 복수의 엔드 디바이스가 경사 하강 계산을 위한 인코딩을 수행하여 계산된 경사도를 파라미터 서버로 전송하는 단계는, 파라미터 서버로부터 인센티브를 획득하기 위해 복수의 엔드 디바이스 간의 이익 극대화(Profit Maximization; PM) 서브게임을 형성하여 서로 경쟁하고, 이익 극대화 서브게임에서 결정된 엔드 디바이스의 최상의 응답에 대하여 상기 파라미터 서버가 단일 팔로워로서 태스크 완료 지연 시간을 최소화하기 위한 로드가 해당 엔드 디바이스에 할당되는 코딩 및 인센티브 기반 분산 컴퓨팅 관리 방법
|
| 14 |
14
제9항에 있어서, 상기 파라미터 서버가 복수의 엔드 디바이스에 대해 인코딩 결과에 따른 인센티브를 분배하는 단계는, 기본 인센티브 분배 및 경쟁 인센티브 분배를 포함하는 인센티브 분배 방식을 이용하여, 복수의 엔드 디바이스에 대한 최소 인센티브를 보장하는 기본 인센티브가 제공됨으로써 복수의 엔드 디바이스의 참여를 유도하고, 모든 복수의 엔드 디바이스로부터 평가 결과를 입력 받으면, 평가 결과에 따른 인센티브가 제공되는 경쟁 인센티브가 복수의 엔드 디바이스에 분배되는코딩 및 인센티브 기반 분산 컴퓨팅 관리 방법
|
| 15 |
15
제14항에 있어서, 상기 기본 인센티브 분배 방식은 복수의 엔드 디바이스의 이익이 미리 결정된 최소값 이하로 되는 것을 방지하기 위해 모든 참여 엔드 디바이스에게 균등하게 분배되는 기본 인센티브가 분배되는 코딩 및 인센티브 기반 분산 컴퓨팅 관리 방법
|
| 16 |
16
제9항에 있어서, 상기 경쟁 인센티브 분배 방식은 인센티브에 대한 복수의 엔드 디바이스 간 경쟁을 통해 복수의 엔드 디바이스가 처리한 태스크의 평가 결과에 비례하여 경쟁 인센티브가 분배되고, 평가 결과는 워크로드(Workload; WL) 및 완료 시간(Completion Time; CT)을 포함하는 평가 기준에 따라 평가되며, 워크로드 기반 경쟁 인센티브는 엔드 디바이스가 처리한 워크로드의 양으로 평가되고, 완료 시간 기반 경쟁 인센티브는 엔드 디바이스의 예상 태스크 완료 지연 시간으로 평가되는 코딩 및 인센티브 기반 분산 컴퓨팅 관리 방법
|
