2009-08-20 34 views
6

Tôi có một nhóm nhóm tùy chỉnh, tạo ra một số chủ đề mà mỗi chủ đề chờ đợi trên sự kiện (tín hiệu) của riêng họ. Khi một công việc mới được thêm vào nhóm luồng, nó sẽ đánh thức luồng miễn phí đầu tiên để nó thực hiện công việc.Chi phí đầu vào do sử dụng Sự kiện

Vấn đề là như sau: Tôi có khoảng 1000 vòng của mỗi khoảng 10'000 lần lặp lại làm. Các vòng lặp này phải được thực thi tuần tự, nhưng tôi có sẵn 4 CPU. Những gì tôi cố gắng làm là để chia các vòng lặp lặp lại 10'000 thành vòng lặp lặp lại 2'500 vòng, tức là một cho mỗi chủ đề. Nhưng tôi phải chờ 4 vòng nhỏ để hoàn thành trước khi chuyển sang lần lặp "lớn" tiếp theo. Điều này có nghĩa là tôi không thể bó các công việc.

Vấn đề của tôi là sử dụng nhóm luồng và 4 luồng chậm hơn nhiều so với thực hiện công việc tuần tự (có một vòng lặp được thực hiện bởi một chuỗi riêng biệt chậm hơn nhiều so với thực hiện trực tiếp trong chuỗi chính tuần tự).

Tôi đang sử dụng Windows, vì vậy tôi tạo sự kiện với CreateEvent() và sau đó đợi một trong số chúng bằng cách sử dụng WaitForMultipleObjects(2, handles, false, INFINITE) cho đến khi chủ đề chính gọi SetEvent().

Dường như toàn bộ sự kiện này (cùng với việc đồng bộ hóa giữa các chủ đề bằng các phần quan trọng) là khá đắt!

Câu hỏi của tôi là: việc sử dụng các sự kiện có "nhiều thời gian" là bình thường không? Nếu vậy, có cơ chế nào khác mà tôi có thể sử dụng và điều đó sẽ tốn ít thời gian hơn không?

Dưới đây là một số mã để minh họa (một số bộ phận có liên quan sao chép từ lớp hồ bơi thread của tôi):

// thread function 
unsigned __stdcall ThreadPool::threadFunction(void* params) { 
    // some housekeeping 
    HANDLE signals[2]; 
    signals[0] = waitSignal; 
    signals[1] = endSignal; 

    do { 
     // wait for one of the signals 
     waitResult = WaitForMultipleObjects(2, signals, false, INFINITE); 

     // try to get the next job parameters; 
     if (tp->getNextJob(threadId, data)) { 
      // execute job 
      void* output = jobFunc(data.params); 

      // tell thread pool that we're done and collect output 
      tp->collectOutput(data.ID, output); 
     } 

     tp->threadDone(threadId); 
    } 
    while (waitResult - WAIT_OBJECT_0 == 0); 

    // if we reach this point, endSignal was sent, so we are done ! 

    return 0; 
} 

// create all threads 
for (int i = 0; i < nbThreads; ++i) { 
    threadData data; 
    unsigned int threadId = 0; 
    char eventName[20]; 

    sprintf_s(eventName, 20, "WaitSignal_%d", i); 

    data.handle = (HANDLE) _beginthreadex(NULL, 0, ThreadPool::threadFunction, 
     this, CREATE_SUSPENDED, &threadId); 
    data.threadId = threadId; 
    data.busy = false; 
    data.waitSignal = CreateEvent(NULL, true, false, eventName); 

    this->threads[threadId] = data; 

    // start thread 
    ResumeThread(data.handle); 
} 

// add job 
void ThreadPool::addJob(int jobId, void* params) { 
    // housekeeping 
    EnterCriticalSection(&(this->mutex)); 

    // first, insert parameters in the list 
    this->jobs.push_back(job); 

    // then, find the first free thread and wake it 
    for (it = this->threads.begin(); it != this->threads.end(); ++it) { 
     thread = (threadData) it->second; 

     if (!thread.busy) { 
      this->threads[thread.threadId].busy = true; 

      ++(this->nbActiveThreads); 

      // wake thread such that it gets the next params and runs them 
      SetEvent(thread.waitSignal); 
      break; 
     } 
    } 

    LeaveCriticalSection(&(this->mutex)); 
} 
+0

chỉnh sửa chính xác câu hỏi của bạn ... – neuro

Trả lời

1

Nếu bạn chỉ song song các vòng lặp và sử dụng so với năm 2008, tôi khuyên bạn nên xem xét OpenMP. Nếu bạn đang sử dụng visual studio 2010 beta 1, tôi khuyên bạn nên xem parallel pattern library, đặc biệt là "parallel for"/"parallel for each" apis hoặc lớp "task group vì những khả năng này sẽ làm những gì bạn đang cố gắng làm, chỉ với ít mã hơn.

Về câu hỏi của bạn về hiệu suất, ở đây nó thực sự phụ thuộc. Bạn sẽ cần phải xem bạn đang lập kế hoạch bao nhiêu công việc trong các lần lặp lại của bạn và chi phí là bao nhiêu. WaitForMultipleObjects có thể khá tốn kém nếu bạn nhấn nó rất nhiều và công việc của bạn là nhỏ mà là lý do tại sao tôi đề nghị sử dụng một thực hiện đã được xây dựng. Bạn cũng cần đảm bảo rằng bạn không chạy trong chế độ gỡ lỗi, dưới trình gỡ lỗi và rằng các tác vụ không bị chặn trên khóa, cấp I/O hoặc cấp phát bộ nhớ và bạn không bị chia sẻ sai. Mỗi trong số này có khả năng phá hủy khả năng mở rộng.

Tôi khuyên bạn nên xem xét điều này dưới dạng profiler như xperf f1 profiler trong studio trực quan 2010 beta 1 (có 2 chế độ đồng thời mới giúp xem ganh đua) hoặc vtune của Intel.

Bạn cũng có thể chia sẻ mã mà bạn đang chạy trong các tác vụ, vì vậy mọi người có thể hiểu rõ hơn về những gì bạn đang làm, vì câu trả lời tôi luôn gặp phải với các vấn đề về hiệu suất là "nó phụ thuộc" và thứ hai , "bạn đã lược tả nó chưa."

Good Luck

-Rick

+0

Cảm ơn câu trả lời của bạn. Tôi sẽ chấp nhận của bạn khi bạn cung cấp các liên kết hữu ích và đề xuất sử dụng OpenMP! – Wookai

1

Bối cảnh chuyển đổi giữa các chủ đề có thể tốn kém quá. Thật thú vị trong một số trường hợp để phát triển một khung công tác mà bạn có thể sử dụng để xử lý công việc của bạn tuần tự với một luồng hoặc với nhiều luồng. Bằng cách này bạn có thể tận dụng tối đa hai thế giới.

Nhân tiện, câu hỏi của bạn chính xác là gì? Tôi sẽ có thể trả lời chính xác hơn với một câu hỏi chính xác hơn :)

EDIT:

Phần sự kiện có thể tiêu thụ nhiều hơn so với xử lý của bạn trong một số trường hợp, nhưng không nên quá đắt, trừ trường hợp xử lý của bạn thực sự là nhanh chóng đạt được. Trong trường hợp này, việc chuyển đổi giữa các thredas cũng rất tốn kém, do đó phần trả lời đầu tiên của tôi về việc làm mọi thứ liên tiếp ...

Bạn nên tìm các nút cổ chai đồng bộ hóa giữa các chủ đề. Bạn có thể theo dõi chủ đề thời gian chờ đợi để bắt đầu với ...

EDIT: Sau nhiều gợi ý ...

Nếu tôi đoán đúng, vấn đề của bạn là sử dụng một cách hiệu quả tất cả các lõi máy tính/vi xử lý của bạn để parralellize một số chế biến essencialy tuần tự.

Hãy đảm bảo rằng bạn có 4 lõi và 10000 vòng để tính toán như trong ví dụ của bạn (trong nhận xét). Bạn nói rằng bạn cần phải chờ 4 đề tài kết thúc trước khi tiếp tục. Sau đó, bạn có thể đơn giản hóa quá trình đồng bộ hóa của mình. Bạn chỉ cần cung cấp cho bốn chủ đề của bạn thr nth, nth + 1, nth + 2, nth + 3 vòng, chờ cho bốn chủ đề để hoàn thành sau đó tiếp tục. Bạn nên sử dụng một điểm hẹn hoặc rào cản (một cơ chế đồng bộ mà chờ cho n đề hoàn thành). Boost có cơ chế như vậy. Bạn có thể xem các cửa sổ triển khai hiệu quả. Hồ bơi thread của bạn không thực sự phù hợp với nhiệm vụ. Việc tìm kiếm một chuỗi có sẵn trong một phần quan trọng là những gì đang giết thời gian CPU của bạn. Không phải là phần sự kiện.

+0

Mmmh, tôi nghĩ câu hỏi của tôi là về chi phí sử dụng sự kiện (chúng thực sự đắt tiền hay tôi làm sai điều gì?). – Wookai

+0

Vâng, chỉnh sửa câu hỏi của bạn sẽ tốt hơn ... – neuro

+1

Cách tiếp cận của neuro có lẽ là đặt cược tốt nhất của bạn. Lựa chọn khác của bạn là thiết kế lại các vòng của bạn để chúng không còn dựa vào nhau, nếu bạn có thể. Bạn có thể phải trả một hình phạt hoàn hảo, nhưng đó là ok: mã đó là x2 chậm hơn nhưng quy mô tuyến tính với số lượng các chủ đề phần cứng thắng tổng thể, phải không? –

1

Nó không phải là đắt tiền, nhưng nếu công việc của bạn hầu như không mất thời gian nào, thì chi phí của các chủ đề và đối tượng đồng bộ sẽ trở nên quan trọng. Thread pool như công việc này tốt hơn nhiều cho công việc xử lý lâu hơn hoặc cho những người sử dụng nhiều IO thay vì tài nguyên CPU. Nếu bạn bị ràng buộc CPU khi xử lý một công việc, hãy đảm bảo bạn chỉ có 1 luồng cho mỗi CPU.

Có thể có các vấn đề khác, làm cách nào để getNextJob lấy dữ liệu của nó để xử lý? Nếu có một lượng lớn dữ liệu sao chép, thì bạn đã tăng đáng kể chi phí của mình một lần nữa.

Tôi sẽ tối ưu hóa nó bằng cách cho phép mỗi chủ đề tiếp tục kéo công việc ra khỏi hàng đợi cho đến khi hàng đợi trống. theo cách đó, bạn có thể chuyển một trăm công việc vào nhóm luồng và các đối tượng đồng bộ sẽ chỉ được sử dụng một lần để khởi động luồng. Tôi cũng sẽ lưu trữ các công việc trong một hàng đợi và chuyển một con trỏ, tham chiếu hoặc vòng lặp tới chúng tới luồng thay vì sao chép dữ liệu.

+0

Tôi đã có ý tưởng tối ưu hóa giống như bạn, tức là cho phép chủ đề kéo công việc mà không phải qua WaitForMultipleObjects(), nhưng trong trường hợp của tôi, tôi có rất ít công việc cho mỗi luồng, vì vậy điều này sẽ không thay đổi nhiều. – Wookai

+0

Tôi nghĩ bạn đã có 2500 cho mỗi chủ đề? Đừng bận tâm - cách khác là kiểm tra OpenMP có thể nhanh hơn và dễ thực hiện hơn. (nghĩa là bạn chỉ cần đặt một pragma trước vòng lặp for và để nó quản lý mọi thứ cho bạn). – gbjbaanb

3

Có, WaitForMultipleObjects là khá tốn kém. Nếu công việc của bạn nhỏ, chi phí đồng bộ hóa sẽ bắt đầu áp đảo chi phí thực sự thực hiện công việc, như bạn đang thấy.

Một cách để sửa lỗi này là gộp nhiều công việc thành một: nếu bạn nhận được công việc "nhỏ" (tuy nhiên bạn đánh giá những thứ đó), lưu trữ nó ở đâu đó cho đến khi bạn có đủ công việc nhỏ với nhau để thực hiện một công việc hợp lý. Sau đó gửi tất cả chúng đến một chuỗi công nhân để xử lý.

Cách khác, thay vì sử dụng tín hiệu, bạn có thể sử dụng hàng đợi một đầu đọc nhiều đầu đọc để lưu trữ công việc của mình. Trong mô hình này, mỗi luồng công nhân cố gắng lấy các công việc ra khỏi hàng đợi. Khi nó tìm thấy, nó thực hiện công việc; nếu không, nó sẽ ngủ trong một thời gian ngắn, sau đó tỉnh dậy và thử lại. Điều này sẽ giảm chi phí cho mỗi tác vụ của bạn, nhưng các chủ đề của bạn sẽ mất CPU ngay cả khi không có công việc phải làm. Tất cả phụ thuộc vào bản chất chính xác của vấn đề.

+0

Vấn đề là như sau: Tôi có khoảng 1000 vòng của mỗi khoảng 10'000 lặp làm gì. Các vòng lặp này phải được thực thi tuần tự, nhưng tôi có sẵn 4 CPU. Những gì tôi cố gắng làm là để chia các vòng lặp lặp lại 10'000 thành vòng lặp lặp lại 2'500 vòng, tức là một cho mỗi chủ đề. Nhưng tôi phải chờ 4 vòng nhỏ để hoàn thành trước khi chuyển sang lần lặp "lớn" tiếp theo. Điều này có nghĩa là tôi không thể bó các công việc. – Wookai

+0

Đặt câu hỏi đó vào câu hỏi;) – neuro

+0

Đó là vấn đề thực sự ... Xem chỉnh sửa của tôi trong câu trả lời của tôi cho 2 xu của tôi ... – neuro

3

Điều này đối với tôi như là một mô hình tiêu dùng của nhà sản xuất, có thể được sử dụng với hai semaphores, một bảo vệ tràn hàng đợi, hàng đợi trống khác.

Bạn có thể tìm thấy một số chi tiết here.

+0

Các semaphores có đắt hơn các sự kiện không? – Wookai

+0

"đắt" là gì? Về tài nguyên? Trong thời gian hạt nhân dành để khóa/mở khóa? –

+0

Tôi không nghĩ có sự khác biệt. Dù sao, một sự khác biệt có thể được nhìn thấy. Bạn luôn có thể đo lường với một hồ sơ. –

2

Xem ra, bạn vẫn đang yêu cầu một công việc tiếp theo sau khi endSignal được phát ra.

for(;;) { 
    // wait for one of the signals 
    waitResult = WaitForMultipleObjects(2, signals, false, INFINITE); 
    if(waitResult - WAIT_OBJECT_0 != 0) 
     return; 
    //.... 
} 
+0

Cảm ơn bạn đã chỉ ra điều đó. Nó không phải là một vấn đề vì endSignal được gọi khi danh sách công việc trống, vì vậy nó sẽ không nhận được bất kỳ công việc nào và sẽ kết thúc chính xác. Nhưng bạn hoàn toàn đúng! – Wookai

1

Dường như sự kiện này toàn bộ điều (cùng với đồng bộ hóa giữa các chủ đề sử dụng quan trọng phần) là khá đắt!

"Đắt" là thuật ngữ tương đối. Máy bay phản lực có đắt không? Xe ô tô? hoặc xe đạp ... giày ...?

Trong trường hợp này, câu hỏi đặt ra là: các sự kiện "đắt tiền" có liên quan đến thời gian thực hiện cho JobFunction để thực thi không? Nó sẽ giúp xuất bản một số số liệu tuyệt đối: Quá trình này mất bao lâu khi "chưa được đọc"? Có phải vài tháng, hoặc một vài femtoseconds?

Điều gì sẽ xảy ra với thời gian khi bạn tăng kích thước bộ chia kích thước? Thử kích thước hồ bơi 1, sau đó 2 rồi 4, v.v.

Ngoài ra, vì bạn đã gặp một số vấn đề với threadpool ở đây trước đây, tôi khuyên bạn nên gỡ lỗi để đếm số lần mà threadfunction của bạn thực sự được gọi ... nó có khớp với những gì bạn mong đợi không?

Chọn hình ngoài trời (không biết gì về hệ thống đích của bạn và giả sử bạn không làm bất kỳ thứ gì 'lớn' trong mã bạn chưa hiển thị), tôi mong đợi "sự kiện trên cao" của mỗi "công việc" được đo bằng micro giây. Có lẽ một trăm hoặc hơn. Nếu thời gian thực hiện để thực hiện các thuật toán trong JobFunction là không nhiều hơn đáng kể so với thời gian này, sau đó đề của bạn có khả năng chi phí cho bạn thời gian hơn là lưu nó.

1

Vì bạn nói rằng nó là nhiều chậm song song so với thực hiện tuần tự, tôi cho rằng thời gian xử lý của bạn cho nội 2500 lặp lại vòng lặp của bạn là rất nhỏ (trong vài phạm vi giây vi mô). Sau đó, không có nhiều bạn có thể làm ngoại trừ xem xét thuật toán của bạn để chia khối lớn hơn của precessing; OpenMP sẽ không giúp đỡ và mọi kỹ thuật đồng bộ hóa khác sẽ không giúp được gì cả bởi vì về cơ bản, tất cả đều dựa vào các sự kiện (vòng quay không đủ điều kiện).

Mặt khác, nếu thời gian xử lý của bạn trong vòng lặp 2500 lặp lại lớn hơn 100 micro giây (trên máy tính hiện tại), bạn có thể gặp phải hạn chế của phần cứng. Nếu quá trình xử lý của bạn sử dụng nhiều băng thông bộ nhớ, việc chia nhỏ bộ xử lý thành bốn bộ xử lý sẽ không cung cấp cho bạn nhiều băng thông hơn, nó sẽ thực sự cung cấp cho bạn ít hơn vì xung đột. Bạn cũng có thể chạy vào các vấn đề của bộ đệm ẩn trong đó mỗi lần lặp 1000 đầu của bạn sẽ tuôn ra và tải lại bộ nhớ cache của 4 lõi. Sau đó, không có giải pháp nào, và tùy thuộc vào phần cứng đích của bạn, có thể không có giải pháp nào.

+0

Cảm ơn thông tin chi tiết! OpenMP đã giúp một chút, nhưng nó chủ yếu là giúp bằng cách cho phép tôi để thoát khỏi hồ bơi chủ đề tùy chỉnh của tôi và dựa vào một cái gì đó đáng tin cậy hơn nhiều. – Wookai

+0

OpenMP có thể giúp bởi vì nó sử dụng chuỗi hiện tại để thực thi. Vì vậy, bạn có ít hơn 20% đồng bộ hóa trong trường hợp của bạn. Ngoài ra nó thường được thực hiện với một vòng quay nhỏ trước khi ngủ, vì vậy nếu thực hiện của bạn là nhanh chóng, nó có thể giúp loại bỏ sự kiện hoàn toàn trong nhiều trường hợp. – Juice

0

Như đã đề cập trước đó, lượng phí bổ sung bằng luồng phụ thuộc vào lượng thời gian tương đối được thực hiện để thực hiện "công việc" mà bạn đã xác định. Vì vậy, điều quan trọng là tìm một sự cân bằng trong kích thước của khối công việc mà giảm thiểu số lượng các mảnh nhưng không để lại bộ vi xử lý nhàn rỗi chờ đợi cho nhóm cuối cùng của tính toán để hoàn thành.

Cách tiếp cận mã hóa của bạn đã tăng số lượng công việc trên cao bằng cách chủ động tìm kiếm một chuỗi nhàn rỗi để cung cấp với công việc mới. Hệ điều hành đã theo dõi điều đó và thực hiện nó hiệu quả hơn rất nhiều. Ngoài ra, chức năng của bạn ThreadPool :: addJob() có thể thấy rằng tất cả các chủ đề đang được sử dụng và không thể ủy nhiệm công việc. Nhưng nó không cung cấp bất kỳ mã trả lại nào liên quan đến vấn đề đó.Nếu bạn không kiểm tra tình trạng này theo một cách nào đó và không nhận thấy lỗi trong kết quả, điều đó có nghĩa là luôn có các bộ xử lý nhàn rỗi. Tôi khuyên bạn nên tổ chức lại mã để addJob() thực hiện những gì được đặt tên - thêm một công việc CHỈ (không tìm hoặc thậm chí quan tâm đến công việc) trong khi mỗi luồng công nhân chủ động nhận được công việc mới khi nó được thực hiện với công việc hiện tại của nó.

Các vấn đề liên quan