현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

쓰레드를 이용하여 소트 하기...

xroot의 이미지
글쓴이: xroot / 작성시간: 월, 2008/05/05 - 10:46오후

학교에서 쓰레드에 관해서 배우고 있습니다..
멀티 태스킹환경에서 쓰레드를 이용하여 속도를 빨리한다.
뭐 이정도로 감잡고 있는데요.
소트하는 경우도 쓰레드를 이용하면 그렇지 않은 경우보다 더 빨리 정렬을 완료 하나요?
프로그램을 못짜서인지 쓰레드를 사용하면 쓰레드 갯수배만큼 느려지네요..
아 정렬 방식은 버블소트를 이용하였고 A라는 행령을 쓰레드의 인수로 넘겼습니다
그리고 각 쓰레드는 대소비교후 하나씩 뒤로 넘겨 결국 가장 큰 숫자가 가장 뒤로 가도록 하였고.
이때 mutex는 대소비교와 교환하는 부분을 통째로 묶었습니다.
프로그램의 IO하는 시간에 다른 작업을 수행시켜 CPU의 노는 시간을 줄이자 그런 취지 인것 같은데 뮤텍스로 통때로 묶어버리면 쓰레드를 사용하는 의미가 있나요?

Forums: 
프로그래밍 QnA
cinsk의 이미지

글쓴이: cinsk / 작성시간: 월, 2008/05/05 - 11:39오후

통째로 묶어버리면 thread 사용하는 의미가 없죠.

대부분 O(n^2) 형태의 sorting 방식은 작업 대상을 전체 set을 보고 하기 때문에 thread 여러 개를 둔다는 것 자체가 큰 의미가 없습니다. 보통은 set을 나누어 sorting하는 방식에서 thread를 쓰는 것을 생각해볼만 하지만, CPU가 단지 하나인 경우, thread를 쓰는 것은 overhead만 커질 가능성이 높습니다. (주의: 이 때 CPU란 thread 처리를 위해 특별한 기능이 없는 CPU를 말함) CPU가 여러 개이고, 각자 RAM에 독립적으로 접근할 수 있다면, thread를 쓰는 것이 의미가 있겠지요.

좀 더 자세한 내용은 직접 찾아보기 바랍니다. :)

"parallel sort"로 google 해 보세요.

참고로 "alpha sort"에 대해서도 알아보기 바랍니다.

AlphaSort: A Cache-Sensitive Parallel External Sort

Multithreaded Architectures and The Sort Benchmark

--
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
Korean Ver: http://www.cinsk.org/cfaqs/

C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
Korean Ver: http://cinsk.github.io/cfaqs/

mach의 이미지

글쓴이: mach / 작성시간: 화, 2008/05/06 - 5:02오후

순차적인 처리를 해야 하는 프로그래밍 로직이 있을 수 있고, 동시에 처리할 수 있는 프로그래밍 로직이 있을 수 있습니다.
쓰레드를 적용하기 위해서는 동시성(병렬성)을 문제에서 찾아서 이 부분을 쓰레드로 처리해야 하는 것 입니다.
소팅방법은 아주 다양한데, 이중 동시성을 가지는 알고리즘을 찾아보세요.

------------------ P.S. --------------
지식은 오픈해서 검증받아야 산지식이된다고 동네 아저씨가 그러더라.

------------------ P.S. --------------
지식은 오픈해서 검증받아야 산지식이된다고 동네 아저씨가 그러더라.

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.