그래프 채색에 의한 타임 슬롯 할당 알고리즘

권보섭(BoSeob Kwon) 한국콘텐츠학회 2008 한국콘텐츠학회논문지 Vol.8 No.5

위성 통신 분야에서 널리 사용되는 시분할 다중 스위칭 시스템은 많은 저대역폭 가입자들로부터 발생되는 트랙픽을 반복되는 프레임에 타임 슬롯을 할당해야 한다. 본 논문에서는 타임 슬롯 할당을 위한 새로운 방법을 제안한다. 기존의 방법인 네트워크 흐름 모델을 사용하지 않고 새로운 방법인 그래프 채색방법을 사용하여 효율적인 타임 슬롯 할당 알고리즘을 제안하였다. 제안된 알고리즘은 주어진 트래픽의 프레임 길이가 2의 멱승일 경우 트래픽을 정확히 반으로 나누어 할당한다. 분할된 트래픽의 프레임 길이가 1이 될 때까지 이 과정을 계속적으로 반복해 분할한다. 제안된 알고리즘의 시간 복잡도는 프레임의 길이가 L이고 스위치 크기가 N인 경우에는 기존의 네트워크 흐름 모델을 사용한 최적의 타임 슬롯 할당 알고리즘의 시간 복잡도는 O (N<SUP>4.5</SUP>) 인데 반해 O (NLlog₂L)이다. A simple Time Division Multiplex(TDM) switching system which has been widely in satellite networks provides any size of bandwidth for a number of low bandwidth subscribers by allocating proper number of time slots in a frame. In this paper, we propose a new approach based on graph coloring model for efficient time slot assignment algorithm in contrast to network flow model in previous works. When the frame length of an initial matrix of time slot requests is 2's power, this matrix is divided into two matrices of time slot requests using binary divide and conquer method based on the graph coloring model. This process is continued until resulting matrices of time slot requests are of length one. While the most efficient algorithm proposed in the literature has time complexity of O (N<SUP>4.5</SUP>) , the time complexity of the proposed algorithm is O (NL log₂L ), where N is the number of input/output links and L is the number of time slot alloted to each link in the frame.

선다형 유형의 합답형 문항에서 부분적 지식이 추측에 미치는 영향

권보섭(Boseob Kwon) 한국컴퓨터교육학회 2021 컴퓨터교육학회 논문지 Vol.24 No.1

선다형 문항은 피험자들의 능력 평가에서 객관적이고 신뢰성이 높은 이유로 평가도구로 많이 사용되고 있지만, 추측의 요인을 없앨 수 없다. 특히 추측의 관점에서 선다형 가운데 합답형은 피험자들이 맹목적인 추측보다는 답가지의 부분적인 지식으로부터 선택지를 추측하려는 경향이 많다. 이 논문은 합답형에서 답가지에 대한 부분적인 지식에 기초하여 추측으로 정답을 맞힐 비율인 문항 추측도를 알고리즘으로 분석하고 이를 고전검사이론에서의 문항 추측도와 비교하였다. 이를 위해 합답형 문항에서 답가지의 진위에 대해 ‘예’ 혹은 ‘아니오’를 ‘1’ 혹은 ‘0’으로 대체하고 답가지의 조합들은 부울 행렬로 나타내었으며 또한 특정 답가지의 진위에 관계없이 추측이 동일하게 되도록 부울 행렬을 사용하여 균형 선택지를 정의하고 이를 바탕으로 부분적인 지식의 개수에 따른 추측의 비율을 재귀식으로 나타냈다. 분석에 의하면 합답형 문항에서 답가지들을 정확히 모르고 정답을 맞히는 추측의 비율이 과소 평가되고 있다는 것이 우리에게 주는 시사점이다. The multiple choice item is widely used as an evaluation tool because it is objective and highly reliable in scoring the ability of subjects. However, it cannot remove the guessing factor. From the point of view of guess, the guess of multiple true-false items one of multiple choice type tend to guess choices from partial knowledge of options rather than blind guess. The paper analyzed the Guessing Parameter, which is the ratio of correct answers by guessing based on partial knowledge in the Multiple True-False Items, and compared the Guessing Parameter in the classical test theory. To this end, ‘True’ or ‘False’ about options in multiple true-false item was replaced with ‘1’ or ‘0’. Combinations of option(choices) of options are represented by a boolean matrix. And a boolean matrix was used to define the balanced choices so that the guess is the same regardless of the true-false of a specific options. Based on this, the ratio of guesses according to the number of partial knowledge is represented by a recursive equation. According to the analysis, it is an implication to us that the proportion of guessing for correct answers without knowing exactly the answers in the Multiple True-False Items is underestimated.

프로그래밍 학습에서 인지양식이 협력적 문제해결력에 미치는 영향

권보섭(Boseob Kwon) 한국컴퓨터정보학회 2018 韓國컴퓨터情報學會論文誌 Vol.23 No.9

Problem solving by programming has a lot of influence on computational thinking improvement. Programming learning has been self-directed based on the individual’s thoughts and principles. However, the revised informatics curriculum in 2015 puts importance on collaborative learning. Collaborative learning emphasizes results differently from cooperative learning, which emphasizes problem-solving processes. And cooperative learning leads to structured learning, such as role sharing and activity stages, within a small group, while collaborative learning leads to unstructured learning. Therefore, it is becoming more in collaborative learning that peer interaction can be affected by learners’ cognitive style. In this paper, we propose the effect of cognitive style on problem solving ability in collaborative learning for problem solving by programming. As a result, collaborative learning was effective in improving problem solving ability and there was no significant difference in cognitive style.

프로그래밍 학습에서 협동학습이 문제해결력에 미치는 효과

권보섭(Boseob Kwon) 한국콘텐츠학회 2014 한국콘텐츠학회논문지 Vol.14 No.6

프로그래밍 학습은 프로그래밍을 통한 문제 해결과정을 경험함으로써 고차원적인 사고력의 향상을 목적으로 하는 경향이 있다. 프로그래밍 학습은 주로 학습자 개인의 사고와 원리를 바탕으로 자기 주도적으로 이루어져 왔다. 그러나 선행 연구들 중, 논리적 사고력과 창의성을 바탕으로 하는 소집단 협동학습이 효과가 있다는 결과가 보고된 바 있다. 이에 본 논문에서는 프로그래밍 학습에서 문제해결과정에 소집단 협동학습을 수행하는 것이 문제 해결력 향상에 미치는 영향을 검증하였다. 이를 위하여 문제해결 5단계를 기본으로 소집단 협동학습을 포함하는 모형을 개발하여 적용하였다. 그 결과 소집단 협동학습은 프로그래밍 학습에서 문제해결력 향상에 효과가 있으며, 인지양식에 대해서는 유의미한 차이가 나타나지 않았다. Programming learning tend to improve the high thinking ability by experiencing problem solving process through programming recently, There are the previous studies that small group cooperative learning has the effect of the learning that is based logical thinking and creativity, while programming learning has relied on individual learner‘s thinking and principles traditionally. In this paper, it was verified the effect on improving the problem solving ability to perform by the small cooperative learning group in a problem solving process of programming learning. For this, it was developed and applied a model that include small cooperative learning group based on the problem solving 5 steps. The results of this study showed that the small cooperative learning group has positive effect of the problem solving ability in programming learning and has no relationship with cognitive style.

우회경로 스위치를 기반한 다중전송 스위치의 설계 및 성능평가

권위남(WiNam Kwon),박재형(Jaehynng Park),조기호(Ki-Ho Cho),김병호(Byungho Kim),권보섭(Boseob Kwon),김진천(Jin Chun Kim),윤현수(Hyunsoo Yoon),박권철(Kwonchul Park) 한국정보과학회 1995 한국정보과학회 학술발표논문집 Vol.22 No.2B

광대역 종합정보통신망에서는 다양한 서비스(service)가 고속의 다중전송 기능을 필요로 한다. 이를 효과적으로 실현하기 위해서는 다중전송 스위치의 개발이 필수적이다. 본 논문에서는 [1,2]에서 제안된 우회경로 스위치를 기반한 다중전송 스위치와 제안된 스위치에서 동작하는 다중전송 알고리즘을 기술한다. 그리고 본 다중전송 스위치와 다중전송 알고리즘의 성능을 시뮬레이션(simulation)을 통하여 평가한다. 본 스위치의 복제망과 라우팅망은 우회경로를 가지는 셔플교환(shuffle exchange)형태의 동일한 구조로 이루어져 있는 특징을 가진다.

웜홀 스위칭하는 양방향 베니언 망에서의 두 단계 멀티캐스트

권위남(Winam Kwon),권보섭(Boseob Kwon),박재형(Jaehyung Park),윤현수(H.Yoon) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.3

A multistage interconnection network is a suitable class of interconnection architecture for constructing large-scale multicomputers. Broadcast and multicast communication are fundamental in supporting collective communication operations such as reduction and barrier synchronization. In this paper, we propose a new multicast technique in wormhole-switched bidirectional multistage banyan networks for constructing large-scale multicomputers. To efficiently support broadcast and multicast with simple additional hardware without deadlock, we propose a two-phase multicast algorithm which takes only two transmissions to perform a broadcast and a multicast to an arbitrary number of desired destinations. We encode a header as a cube and adopt the most upper input link first scheme with periodic priority rotation as arbitration mechanism on contented output links. We coalesce the desired destination addresses into multiple number of cubes. And then, we evaluate the performance of the proposed algorithm by simulation. The proposed two-phase multicast algorithm makes a significant improvement in terms of latency. It is noticeable that the two-phase algorithm keeps broadcast latency as efficient as the multicast latency of fanout 2^m where m is the minimum integer satisfying 2^m≥√N ( N is a network size). 다단계 상호 연결망은 대규모 멀티컴퓨터의 대표적인 연결망 구조이다. 브로드캐스트와 멀티캐스트 통신은 캐쉬 관리, 리덕션, 베리어 동기화와 같은 협동 통신을 지원하기 위한 기반 기술이다. 본 논문은 대규모 멀티컴퓨터 시스템을 구성하기에 적합한 웜홀 스위칭하는 양방향 베니언 망에서 동작하는 멀티캐스트 기법을 제안한다. 제안하는 기법은 간단한 하드웨어하에서 교착상태를 일으키지 않고 두 번의 전송 단계를 거침으로써 멀티캐스트와 브로드캐스트를 수행한다. 또한, 원하는 목적 노드의 주소를 큐브로 병합하고, 헤더는 단일 큐브로 인코딩된다. 출력 링크에 경쟁이 발생하면 가장 상위 입력 링크로 부터 들어온 플릿에게 우선 순위를 줌으로써 교착상태를 방지한다. 제안하는 기법을 시뮬레이션을 통해서 통신지연 시간의 관점에서 다른 기법과 비교 평가함으로써 제안하는 멀티캐스트 기법의 성능이 우수함을 보였다. 또한, 제안하는 브로드캐스트 기법은 팬아웃이 2^m ( 2^m≥√N 인 최소의 정수, N 은 시스템 크기)인 멀티캐스트의 성능과 유사한 월등한 성능을 낸다는 것을 보였다.

ATM 스위치를 이용한 프로세서간 통신에 있어서 최적의 메시지 크기

박혜숙(Hea-Sook Park),권보섭(Boseob Kwon),송광석(Kwang-Suk Song) 한국정보과학회 1997 한국정보과학회 학술발표논문집 Vol.24 No.1A

본 논문에서는 ATM 스위치를 이용한 프로세서간 메시지 통신에 있어서, ATM 스위치에서 셀 전송 오류가 발생할 확률에 따른 메시지의 오류 발생률을 메시지의 크기에 대하여 계산한다. 또한 메시지 오류 복구를 고려한 메시지 재전송 확률을 계산하여 ATM 스위치로 전달되는 전체 셀의 수를 메시지 크기에 따라서 구한다. 결과적으로 본 논문에서는 전송하고자 하는 사용자 메시지 크기가 29 개의 셀로 구성된 1368 바이트일 경우에 재전송을 포함한 송신 셀의 수가 최적이었다. 본 논문에서 고려한 셀 오류는 균등하게 발생한다고 가정하였으며, 메시지 오류에 따른 메시지 재전송에 걸리는 오버 헤드 시간은 고려하지 않았다.

재순환 집중기를 이용한 직렬 반얀 스위치의 설계 및 성능 평가

박재형(Jaehyung Park),권보섭(Boseob Kwon),윤현수(Hyunsoo Yoon) 한국정보과학회 1996 정보과학회논문지 : 시스템 및 이론 Vol.23 No.1

본 논문에서는 기본 구현 블럭으로 반얀 네트워크를 이용하고, 출력버퍼에 다수의 접근점을 제공하는 출력버퍼 기법의 재순환 집중기를 이용한 직렬 반얀 스위치를 제안한다. 제안된 스위치를 구성하는 여러개의 라우팅 반얀 네트워크와 두개의 집중기는 굴절 라우팅 기법의 반얀 네트워크로 동일하게 구현되기 때문에 집중기를 위한 추가적인 하드웨어 비용이 증가하지 않는다. 또한, 스위치 구조 내부에 버퍼가 없는 특성으로 인해서 셀을 라우팅하는데 고정된 지연을 보장하므로 셀간의 순서를 유지할 수 있다. 본 논문에서는 제안된 스위치의 성능을 수치적으로 분석하였으며, 적은 하드웨어 비용으로 원래의 직렬 반얀 스위치와 동일한 셀손실율을 유지함을 보인다. In this paper, we propose a tandem banyan switch with recirculating concentrators employing the banyan network as a basic building block, which uses the output-buffering scheme and provides multiple access points to the output buffer. In the proposed switch, a low hardware cost is achieved by employing two concentrators which are equivalently constructed from the banyan network with deflection routing comprising the overall switch. The proposed switch guarantees the fixed delays in routing cells due to its unbuffered property, therefore it can preserve cell sequence. This paper numerically analyzes the performance of the proposed switch and shows that it maintains as same performance as the original tandem banyan switch with a low hardware cost.

다중 경로를 제공하는 고속 패킷 스위치에 대한 연구

김병호(Byungho Kim),권보섭(Boseob Kwon),윤현수(Hyunsoo Yoon),조정완(Jungwan Cho) 한국정보과학회 1994 한국정보과학회 학술발표논문집 Vol.21 No.2B

최근 10여년간 고속 패킷 스위칭 시스템을 위한 많은 연구가 이루어졌다. 기존에 제안된 스위치들은 그 크기가 대용량화되고 요구되는 고성능(10^-9 이하의 패킷 손실률)을 만족시키기에는 전체 스위치가 복잡해지고 경제적으로 비효율적이라는 문제점을 가지고 있다. 본 논문에서는 스위치를 설계함에 있어 간단한 구조를 통한 확장성과 비용의 효율성에 주목하면서 확장이 용이하고 고성능 및 대용량 N×N(N > 2000) ATM 스위칭 시스템에 적합한 패킷 스위치를 제안한다. 제안하는 스위치는, k × k+1 스위치는 내부적으로 블록킹이 없다는 성질을 기반으로 하고, 내부 블록킹이 없고 자체 라우팅 기능을 갖으며 계층 구조 방식에 따라 서로 연결된 여러개의 스위칭 평면들로 구성된다. 그 특성으로는 구조의 단순성과 함께 낮은 패킷 손실률에 비하여 그 비용이 효율적이라는 것이다. 그리고, 2log₂N 이하의 짧은 스위칭 지연 시간을 제공한다. 성능 분석 결과의 한 예로 13개의 스위칭 평면으로 이루어진 1024 × 1024 스위치는 90 퍼센트 부하에서 10^(-9)의 패킷 손실률을 나타내고 이 때의 스위치 비용은 13-repicated banyan과 유사하다.

내부 버퍼가 있는 확장 배년 네트워크의 성능 분석

송효정(Hyojeong Song),권보섭(Boseob Kwon),윤현수(Hyunsoo Yoon) 한국정보과학회 1999 정보과학회논문지 : 시스템 및 이론 Vol.26 No.5

기본 배년 네트워크의 내부 링크를 확장계수(dilation degree)배만큼 확장한 확장 배년 네트워크(dilater banyan network)는 기존 병렬처리 컴퓨터나 ATM 스위칭 시스템을 위한 효율적인 통신 하부 구조로서 여겨져 왔다. 본 논문에서는, 특히 각 스위치 소자 내부에 버퍼가 있는 확장 배년 네트워크의 성능 분석 모델을 마코프 체인에 기초하여 제안한다. 제안한 분석모델에 의해 도출된 네트워크 지연시간과 정규처리율의 값을 모의실험 결과와 비교하고, 네트워크 부하가 높고 확장 계수가 작은 경우를 제외하고는 두 결과값이 항상 일치함을 보인다. 이러한 확장 배년 네트워크는 스위치의 크기와 관계없이 확장 계수가 3이상이면 이상적인 처리율과 지연시간을 나타낸다. Dilated banyan networks have been regarded as a promising subsystem of parallel computers and ATM switching systems. In this paper, we propose a performance model, based on a Markov chain, for dilated banyan networks with internal buffers. With the proposed performance model, we can produce their network delay and normalized throughput, which, at almose all cases, accord with values from simulation experiments. The both values approximate to ideal ones irrespective of network size, if dilation degree is 3 or more.