The Space-Sharing Scheduling(S³) Technique and its Performance Evaluation for Multithreaded Computers

Nam, Young-Ho 新羅大學校 1996 論文集 Vol.41 No.1

대단위 병렬성을 지원하는 다중스레드 컴퓨터가 폰 노이만 및 데이타플로우 다중프로세서 컴퓨터에서 발생할 수 있는 여러가지 문제점들을 극복하기 위하여 그동안 널리 연구되었다. 다중스레드 컴퓨터 상에서 시분할 스케쥴링 기법의 문제점은 프로그램에 내재된 병렬성이 시스템이 지원할 수 있는 병렬성보다 적은 경우에 다중스레드 컴퓨터의 성능이 전반적으로 저하된다는 것이다. 본 논문에서는 이러한 문제점을 해결하기 위한 하나의 방안으로 다중프로그래밍과 병렬처리를 동시에 지원하는 공간분할 스케쥴링(S3) 기법을 제안하고 관련 알고리즘을 설계한다. S3 기법은 스레드 스케쥴링시 다중스레드 컴퓨터에서 발생할 수 있는 스케쥴링 병목현상을 제거하기 위해 선행처리, 광역 스케쥴링 그리고 지역 스케쥴링의 세 단계로 실행된다. 선행처리 단계에서는 스레드 그래프로부터 스케쥴링 정보를 예측하고 프로세서 부하 균등화를 위하여 스레드 그래프를 군집화한다. 광역 스케쥴링 단계에서는 지역 스케쥴러와 스레드 그래프가 필요로 하는 프로세서를 각 스레드 그래프에게 할당하낟. 지역 스케쥴링 단계에서는 스레드의 입력 동기화 정보와 가장 늦은 실행 완쇼 가능 시간 정보를 기반으로 스레드를 스케쥴링 한다. 제안한 S3 기법의 실행 시간 복잡도는 스레드 갯수(|V0|)와 프로세서 갯수(|P?|)에 대해 O(|V0|×|P?|)이며, 동적 시분할 스케쥴링을 수행하는 SAS(Self-Adaptive Scheduling) 기법에 비해 평균 시스템 응답 시간은 약 50%~70% 정도 감소한 반면, 평균 시스템 처리율과 평균 시스템 이용률은 각각 2.5배와 1.75배 증가하였다. In order to overcome several problems related to either von Neumann or dataflow multiprocessor system, multithreaded computers, which can provide the massive parallelisms, have been widely investigated. One of the problems caused by applying time-sharing scheduling to a multithreaded computer is that if the degree of parallelism embedded in a program is les than that supported by it, its overall perfomance will be degraded significantly. In this paper, we attempt to resolve the problem by proposing space-sharing scheduling(S³) technique and designing related scheduling algorithms. Our technique utilizes both multiprogramming and parallel processing, simultaneously. It consists of three steps such as preprocessing, global scheduling and local sheduling to eliminate scheduling bottleneck in the multithreaded computer. At the first step, we forecast scheduling informations of a thread graph, and cluster two or more threads into one in order for processor to be load balancing. At the second step, the thread graph is alloated a local scheduler along with as many thread processors as needed by it. The final step is responsible for scheduling the threads based on given informations on their synchronizations and latest execution completion times of threads. The run-time complexity of S³is ??, where ?? and ?? are the number of threads and the number of processor, respectively. When comparing ours with SAS (Self-Adaptive Scheduling) technique from simulation result, we find that the average system response time is decremented roughly by 50%∼70% while the average system throughput and utilization rate are incremented by at least 2.5 times and 1.75 times, respectively.

큐를 이용한 다중스레드 방식의 웹 크롤링 설계

김효종,이준연,신승수 중소기업융합학회 2017 융합정보논문지 Vol.7 No.2

본 연구의 목적은 광역 네트워크로 연결된 다수의 봇을 활용하여 단일처리 방식의 시간 지연의 문제점과 병렬처리 방식의 비용증가, 인력낭비에 대한 문제점을 해결할 수 있는 큐를 이용한 다중스레드 방식의 웹 크롤링을 연구한다. 본 연구는 큐를 이용한 다중스레드 방식의 시스템 구성을 바탕으로 독립된 시스템에서 실행하는 어플리케이션을 설계하고 분석한다. 큐를 이용하여 다중 스레드 방식의 웹 크롤러 설계를 제안한다. 또한, 웹 문서의 처리량을 수식에 따라 클라이언트와 스레드 별로 나누어 분석하고, 각각 효율성 비교를 통해 최적의 클라이언트의 개수와 스레드의 개수를 확인 할 수 있다. 제안하는 시스템의 설계 방식은 분산처리를 기반으로 각각의 독립된 환경에서의 클라이언트는 큐와 스레드를 이용하여 빠르고 신뢰성이 높은 웹 문서를 제공한다. 특정 사이트를 대상으로 하는 웹 크롤러 설계가 아닌 범용 웹 크롤러에 큐와 다중 스레드를 적용하여 다양한 웹 사이트를 빠르고 효율적으로 탐색 및 수집하는 시스템이 필요하다. The purpose of this study is to propose a multi-threaded web crawl using queues that can solve the problem of time delay of single processing method, cost increase of parallel processing method, and waste of manpower by utilizing multiple bots connected by wide area network Design and implement. This study designs and analyzes applications that run on independent systems based on multi-threaded system configuration using queues. We propose a multi-threaded web crawler design using queues. In addition, the throughput of web documents can be analyzed by dividing by client and thread according to the formula, and the efficiency and the number of optimal clients can be confirmed by checking efficiency of each thread. The proposed system is based on distributed processing. Clients in each independent environment provide fast and reliable web documents using queues and threads. There is a need for a system that quickly and efficiently navigates and collects various web sites by applying queues and multiple threads to a general purpose web crawler, rather than a web crawler design that targets a particular site.

융통성 있는 스레드 분할 시스템 설계와 평가

조선문 ( Sun-moon Jo ) 한국인터넷정보학회 2007 인터넷정보학회논문지 Vol.8 No.3

다중스레드 모델은 긴 메모리 참조 지체 시간과 동기화의 문제점을 해결할 수 있다는 점에서 대규모 병렬 시스템에 매우 효과적이다. 다중스레드 병렬기계를 위하여 Non-Strict 함수 프로그램을 번역할 때 가장 중요한 것은 순차적으로 수행될 수 있는 부분을 찾아내어 스레드로 분할하는 것이다. 기존의 분할 알고리즘은 조건식의 판단식, 참실행식, 거짓실행식을 기본 블록으로 나누고 각각에 대하여 지역 분할을 적용한다. 이러한 제약은 스레드의 정의를 약간 수정하여 스레드 내에서의 분기를 허용한다면 좀더 좋은 분할을 얻을 수 있다. 스레드내에서의 분기는 병렬성을 감소시키거나 동기화의 횟수를 증가시키거나 또는 교착상태를 발생시키는 등 스레드 분할의 기본 원칙을 어기지 않으며 오히려 스레드 길이를 증가시키거나 동기화 횟수를 줄이는 장점을 가질 수 있다. 본 논문에서는 조건식의 세 가지 기본 블록을 하나 또는 두 개의 기본 블록으로 병합함으로서 스레드 분할을 향상시키는 방법을 제안한다. Multithreaded model is an effective parallel system in that it can reduce the long memory reference latency time and solve the synchronization problems. When compiling the non-strict functional programs for the multithreaded parallel machine, the most important thing is to find a set of sequentially executable instructions and to partitions them into threads. The existing partitioning algorithm partitions the condition of conditional expression, true expression and false expression into the basic blocks and apply local partitioning to these basic blocks. We can do the better partitioning if we modify the definition of the thread and allow the branching within the thread. The branching within the thread do not reduce the parallelism, do not increase the number of synchronization and do not violate the basic rule of the thread partitioning. On the contrary, it can lengthen the thread and reduce the number of synchronization. In the paper, we enhance the method of the partition of threads by combining the three basic blocks into one or two blocks.

A method translating Multithreaded Models to Object-Oriented models

Lee, Kab-Lae 김천과학대학 2001 김천과학대학 논문집 Vol.27 No.-

다중스레드 모델(Multithreaded models)은 폰 노이만(von Neumann) 모델의 실행 지역성(execution locality)과 데이터플로우 모델의 비동기적 자료 가용성(asynchronized and data availability), 내재적 병렬성(inner parallelism)을 혼합한 모델로 확장형 병렬 기계(scalable parallel machine)를 구성하는데 적당한 실행 모델이다. 다중스레드 모델은 이 모델이 실행되는 플랫폼에 따라 각긴 다른 실행 모델을 가져야 한다. 그 이유는 레지스터의 개수나 명령어의 구조 등이 각각의 실행 환경과 기계마다 다르기 때문이다. 그러나 각기 다른 환경에 대해서 적절한 실행 모델을 개발하는 것은 많은 노력과 비용을 필요로 한다. 따라서 효과적인 중간 언어(intermediate language)를 개발하는 것과 다양한 플랫폼에 적용 가능한 가상기계를 개발하는 것이 중요하다. 번역기(translators)는 중간 언어를 기준으로 전위부(front-end)와 후위부(back-end)로 구분할 수 있는데, 전위부는 에러를 조작하기 위해 사용되고, 특별한 머신 구조에 맞게 코드를 생성하기 위해서는 후위부를 사용한다. 따라서 전위부에서 개발된 중간 언어는 후위부에 종속되지 않고 동작할 수 있다 그래서 객체지향언어인 자바언어의 바이트 코드를 중간코드로 사용하면 많은 이기종간에 공통적으로 사용할 수 있는 유용성을 보장받을 수 있다. 즉, 스레드 코드의 실행을 자바 바이트 코드로 변환할 수 있다면 다양한 플랫폼에서 추가적인 비용 없이 처리할 수 있다. 그래서 스레드 코드를 자바 바이트 코드로 변환하는 번역기를 구현 하는 방법은은 매우 중요하다. 본 논문은 자바 가상기계에서 다중스레드 코드를 수행할 수 있도록 하기 위해서 플랫폼 독립적인 중간언어를 설계하고 구현한다. 또한 중간언어를 통해서 멀티스레드 코드를 객체지향언어인 자바 가상기계에서 실행한 결과를 분석한다.

다중스레드 구조를 위한 함수형 언어의 중첩루프 펼침

하상호 한국정보과학회 2002 정보과학회논문지 : 소프트웨어 및 응용 Vol.29 No.11

Id 언어와 같은 함수형 언어의 중천루프에 포함된 미세한 수준의 대규모 병렬성을 다중스레드 구조상에서 이용하려면 프로세서뿐만 아니라, 이름공간을 위한 상당히 말은 기억공간 등의 자원이 추가로 요구된다. 이러한 병렬성을 포함하는 중첩루프론 시스템 자원 제한 없이 무분별하게 펼쳐서 실행하려고 한다면, 실행도중 기억공간의 자원의 고갈로 인하여 프로그램의 실행이 중단될 수 있다. 또한, 루프의 펼침에 따른 부담으로 인하여 프로세서의 수에 비해서 루프를 지나치게 많이 펼치는 경우에, 병렬 수행의 효과가 상당히 떨어질 수 있다. 본 논문에서는 함수형 언어의 중첩루프를 다중스레드 구조상에서 효과적으로 펼쳐서 실행할 수 있는 알고리즘을 제안하고 분석한다. 제안된 알고리즘의 특성은 주어진 중첩루프를 펼칠 시점에 프로세서 수와 기억공간의 현재 사용 가능한 시스템 자원 양에 제한하여 안전하면서도 가능한 최적으로 펼친다는데 있다. We need an enormous amount of memories for name spaces as well as additional processors if we are to effectively exploit a massively parallelism in nested loops of functional languages such as Id. If there is no sufficient amount of memories enough to exploit that parallelism, the execution of programs can be aborted during the unfolding of loops. Additionally, if loops are overunfolded, compared with the number of processors available, the system performance can be degraded severely due to the overhead of loop unfolding. This paper suggests and analyzes an algorithm which can be used to effectively unfold nested loops of functional languages on multithreaded architectures. This algorithm has a feature to unfold a given nested loop safely and near optimally, considering the system resources of processors and memories available when the loop is to be unfolded.

Improvement in Reconstruction Time Using Multi-Core Processor on Computed Tomography

천권수(Kwon Su Chon) 한국방사선학회 2015 한국방사선학회 논문지 Vol.9 No.7

전산화단층촬영에서 재구성 과정은 상당한 시간이 요구된다. 단면 영상의 품질을 높이기 매트릭스 크기를 증가시키면 재구성 시간이 매우 빠른 속도로 증가한다. 다중코어 프로세서는 오늘날 광범위하게 사용되고 있으며, 다중코어 프로세서의 다중 스레드를 이용하여 계산 시간을 줄이는 것이 가능하다. 본 연구는 다중 스레드로 CT의 재구성 시간을 개선하였다. 다중 스레드를 위해 Pthread와 OpenMP를 이용하였고, 재구성 과정에서 많은 시간이 소비되는 컨볼루션과 역투역 과정을 자세히 조사하였다. Pthread와 OpenMP 모두 스피드업과 효율성 측면에서 비슷한 성능을 나타내었다. The reconstruction on the computed tomography requires much time for calculation. The calculation time rapidly increases with enlarging matrix size for improving image quality. Multi-core processor, multi-core CPU, has widely used nowadays and has provided the reduction of the calculation time through multi-threads. In this study, the calculation time of the reconstruction process would improved using multi-threads based on the multi-core processor. The Pthread and the OpenMP used for multi-threads were used in convolution and back projection steps that required much time in the reconstruction. The Pthread and the OpenMP showed similar results in the speedup and the efficiency.

다중스레드를 이용한 분산 환경에서의 이미지 검색 에이전트

차상환(Sang-Hwan Cha),김순철(Soon-Cheol Kim),황병곤(Byung-Kon Hwang) 한국멀티미디어학회 2005 멀티미디어학회논문지 Vol.8 No.3

다중스레드 모델의 성능 향상을 위한 가용 레지스터 기반 캐슁 기법

고훈준,권영필,유원희,Go, Hun-Jun,Gwon, Yeong-Pil,Yu, Won-Hui 한국정보처리학회 2001 정보처리학회논문지 A Vol.8 No.2

A multithreaded model is a hybrid one which combines locality of execution of the von Neumann model with asynchronous data availability and implicit parallelism of the dataflow model. Much researches that have been made toward the advanced performance of multithreaded models are about the cache memory which have been proved to be efficient in the von Neumann model. To use an instruction cache or operand cache, the multithreaded models must have cache memories. If cache memories are added to the multithreaded model, they may have the disadvantage of high implementation cost in the mode. To solve these problems, we did not add cache memory but applied the method of executing the caching by using available registers of the multithreaded models. The available register-based caching method is one that use the registers which are not used on the execution of threads. It may accomplish the same effect as the cache memory. The multithreaded models can compute the number of available registers to be used during the process of the register optimization, and therefore this method can be easily applied on the models. By applying this method, we can also remove the access conflict and the bottleneck of frame memories. When we applied the proposed available register-based caching method, we found that there was an improved performance of the multithreaded model. Also, when the available-register-based caching method is compared with the cache based caching method, we found that there was the almost same execution overhead.

다중스레드 구조에서 함수 언어 루프의 효과적 실행

하상호(Sang Ho Ha) 한국정보처리학회 2000 정보처리학회논문지 Vol.7 No.3

Multithreading is attractive in that it can tolerate memory latency and synchronization by effectively overlapping communication with computation. While several compiler techniques have been developed to produce multithreaded codes from functional languages programs, there still remains a lot of works to implement loops effectively. Executing loops in a style of multithreading usually causes some overheads, which can reduce severely the effect of multirheading. This paper suggests several methods in terms of architectures or compilers which can optimize loop execution by multithreading. We then simulate and analyze them for the matrix multiplication program.

정보통신기술 실습사례 : 병행서버모델의 데이터 전송시간 측정

손명락,이용진 대한공업교육학회 2008 대한공업교육학회지 Vol.33 No.1

The objective of this study is to show practice example let student experience about concurrent servers based multi-processes and multi-thread among the principles of data communication in ICT(information and communications technology). For this, we first implement multi-process server(fork server) and multi-thread server(thread server), and multi-thread client(thread client), Secondly, for experimental environment, we developed small ethernet networks and measure data transfer time with relation to the number of users. Experimental results show that mean transfer time of thread server is less than that of fork server by 20~61 % on average. Furthermore, it is found that the difference of data transfer time between fork server and thread server is proportional to that of the number of users. Main reason of performance difference dues to the difference between process forking time and thread creation time. We can also find that context switching for process and thread affects the load of web server. Our presentation and experimental results can be applied to used as the educational practice materials with which student can experience data communication principles. 본 연구의 목적은 정보통신기술 영역의 데이터 통신 원리 중에서 다중프로세스 방식과 다중 쓰레드 방식의 병행서버에 대해 직접 체험할 수 있는 실습사례를 제시하는 데 있다. 이를 위해 먼저 다중 프로세스 방식인 포크 서버(fork server)와 다중 쓰레드 방식인 쓰레드 서버(thread server), 그리고 쓰레드 클라이언트(thread client)를 구현하였다. 다음에 실험환경으로서 이더넷(ethernet)을 이용한 소규모 네트워크를 구성하였으며 사용자 수에 따른 데이터 전송시간을 측정하였다. 데이터 전송시간을 측정한 결과, 쓰레드 서버가 포크 서버에 비해 약 20~61%의 전송시간 절감율을 보였으며 두 서버 모델 간 전송시간 차이는 사용자 인원수에 비례하였다. 두 서버 모델 간 발생하는 성능차이의 주된 원인은 프로세스 포크(fork)와 쓰레드 생성에 소요되는 시간이 다르기 때문이다. 아울러, 프로세스 간, 쓰레드 간 스케줄링에서 발생하는 문맥전환(context switching) 역시 웹 서버의 부하에 영향을 주는 것을 알 수 있었다. 본 연구를 통해 제시된 실습사례와 측정된 실험데이터는 학교현장에서 수업시간에 데이터통신 원리에 대해 직접 체험할 수 있는 교육적 실습자료로 활용될 수 있다.