From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 29457 invoked by alias); 5 Jun 2019 20:36:32 -0000 Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org Received: (qmail 29449 invoked by uid 89); 5 Jun 2019 20:36:32 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-1.8 required=5.0 tests=AWL,BAYES_00,BODY_8BITS,FREEMAIL_FROM,GARBLED_BODY,HTML_MESSAGE,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=no version=3.3.1 spammy=waits, H*f:sk:CAO9iq9, H*f:sk:eac1d7f, misunderstand X-HELO: mail-yw1-f42.google.com Received: from mail-yw1-f42.google.com (HELO mail-yw1-f42.google.com) (209.85.161.42) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 05 Jun 2019 20:36:30 +0000 Received: by mail-yw1-f42.google.com with SMTP id v189so6002096ywe.1 for ; Wed, 05 Jun 2019 13:36:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=jmg7dFnOEBf8jcx5Li1CSHQZIRfsT3mi0yzN0gClmF8=; b=T9iJ2vRRq9dPOlrM4Luiq8an7GDOmzRjok/OOVxeq9PUAS2q+AYWrQPRN1neTYlp/u /SQaGOaiOR67gJRWliybkEMmOJvp0uAwCxkw1usgReGgufq6CgMhdAYKJo/muRp1fkCm GzQJdLxDN5mgHAN/k0ljDiGWey8ODlnn05f7Kg6ODcmoTqS+jVhr9DQBxl7kU8csEueV 1htTYLk0mPybhZt/cmThXupjFtPCpwKoecNiCPGjbvAFhpaqi//CrbeLWXkYAc+xsw6P iFnbXobnFxLM14FK3goNUnAe0fT88GAnXDSl+dzUIIu6uKUsOS5nwSzp7R4YSmzTcgsM 1EXA== MIME-Version: 1.0 References: <20190603182101.GS19695@tucnak> In-Reply-To: From: Janne Blomqvist Date: Wed, 05 Jun 2019 20:36:00 -0000 Message-ID: Subject: Re: [GSoC'19, libgomp work-stealing] Task parallelism runtime To: =?UTF-8?B?6rmA6rec656Y?= Cc: gcc mailing list , Jakub Jelinek Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-IsSubscribed: yes X-SW-Source: 2019-06/txt/msg00032.txt.bz2 On Wed, Jun 5, 2019 at 10:42 PM =EA=B9=80=EA=B7=9C=EB=9E=98 wrote: > > On Wed, Jun 5, 2019 at 9:25 PM =EA=B9=80=EA=B7=9C=EB=9E=98 wrote: > > > > > > Hi, thanks for the detailed explanation. > > > I think I now get the picture. > > > Judging from my current understanding, the task-parallelism currently > works as follows: > > > 1. Tasks are placed in a global shared queue. > > > 2. Workers consume the tasks by bashing the queue in a while loop, > just as self-scheduling (dynamic scheduling)/ > > > > > > Then the improvements including work-stealing must be done by: > > > 1. Each worker holds a dedicated task queue reducing the resource > contention. > > > 2. The tasks are distributed in a round-robin fashion > > > For nested task submission (does OpenMP support that?) you probably > > want to submit to the local queue rather than round-robin, no? > > > > Hi Janne, > > I believe you're talking about spawning child tasks within an already > running task, which I believe is supported by OpenMP. > > In this case, pushing to the local queue could introduce a deadlock if the > master thread waits on the spawned tasks. > > A short one though since work-stealing can resolve the deadlock. > > A better way to handle this is to round-robin the child tasks to the > queues excluding the queue of the thread consuming the current task. > > Then waiting on the tasks should never cause a deadlock. > > Or did I misunderstand your question? > > Maybe there is a specific reason for avoiding avoid round-robin that I > missed? > Better cache locality. Another option, which I guess starts to go out of scope of your gsoc, is parallel depth first (PDF) search (Blelloch 1999) as an alternative to work stealing. Here's a presentation about some recent work in this area, although for Julia and not OpenMP (no idea if PDF would fit with OpenMP at all): https://www.youtube.com/watch?v=3DYdiZa0Y3F3c --=20 Janne Blomqvist