Received: by 2002:ad5:474a:0:0:0:0:0 with SMTP id i10csp1002491imu; Mon, 5 Nov 2018 12:09:45 -0800 (PST) X-Google-Smtp-Source: AJdET5dJtW5RFEIIHYfJ1GWK3nOK8D6DvFQcSGL0aZi1C9HjRt1oPxwFoWqq98miNy/bWcHqI8ey X-Received: by 2002:a63:b90a:: with SMTP id z10-v6mr21266179pge.221.1541448585830; Mon, 05 Nov 2018 12:09:45 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1541448585; cv=none; d=google.com; s=arc-20160816; b=PXeF8sIEiqr7ZTG0/z6ZG9Z1URshiAG17Ig4+P4csSLUSaPbKV99fNA4WAXhky/hRd KWqmSBc5jwMT8Xw2mHjqnhnFpT7qRslAID9VIw4jXkNqLkhANbmo2HLRZLjpSf/E6yk9 v57hwu9jA/2MwApITszJl9NM2hi6q+Z83tf9yylbxz5reNPNhKcuN+q88kYtiHT8Lp48 RUt9F7vuDoY8TX806ykqVK5j+ugsD6inD6zpNxmMzYaaDB/bfb27wL0iZjZbBND4VAv1 3YBDdJvHEo/pBNEYGUDHGqjUpXmxOoK5eG+t7ZjVd6r5LXMXX1jW/Twt+3UKQTPz7Khu 0QEQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:content-transfer-encoding :content-language:in-reply-to:mime-version:user-agent:date :message-id:organization:from:references:cc:to:subject :dkim-signature; bh=5vMyW/Jps6w9tpZOvnsTAHZKb9apR9/voHFFyWKajM0=; b=g7KAaO2PK+pT1VSJCOmvogx65MrLBx+r0mfXH9649VHiesuZSs024CU34jQW3GnETQ MiEza4Uy3WZOmTPmWiHM/jMCB6dNiQTfBm0kdHnxsG4vQPoSoFGfDiijlNUIE6h0f611 OMeyNicJ/op6A5Qbgs9pxPTaALD1gFGyrLGf+6fZE8zo0m47rGlF5HTszGBOYlGg+7E8 rxNgffx0eHA3XnEDDxFSl/ukeEo4jAdbe7KPpEap37zfpPpIhIQu0wMjePg3BpnqcR9t WkC4I4/SLfvP6jqgJqGiDk9JwiQ7aOmLqEdI0vb+ey4NuV3TkEOAx05ED5kcb9Ga0MjL dS1w== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@oracle.com header.s=corp-2018-07-02 header.b="fr/SvRbt"; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=oracle.com Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id c3-v6si20065799pll.3.2018.11.05.12.09.29; Mon, 05 Nov 2018 12:09:45 -0800 (PST) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; dkim=pass header.i=@oracle.com header.s=corp-2018-07-02 header.b="fr/SvRbt"; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=oracle.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726399AbeKFFaR (ORCPT + 99 others); Tue, 6 Nov 2018 00:30:17 -0500 Received: from aserp2120.oracle.com ([141.146.126.78]:54732 "EHLO aserp2120.oracle.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725139AbeKFFaR (ORCPT ); Tue, 6 Nov 2018 00:30:17 -0500 Received: from pps.filterd (aserp2120.oracle.com [127.0.0.1]) by aserp2120.oracle.com (8.16.0.22/8.16.0.22) with SMTP id wA5K63kh081462; Mon, 5 Nov 2018 20:08:25 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=subject : to : cc : references : from : message-id : date : mime-version : in-reply-to : content-type : content-transfer-encoding; s=corp-2018-07-02; bh=5vMyW/Jps6w9tpZOvnsTAHZKb9apR9/voHFFyWKajM0=; b=fr/SvRbtV0ZG86bWOWr0ldIJtkLi1ayblvA0uZ+w5VleSrEVBsmvxjlFZ+iT/mADe3kJ fdxVNwiCAgfkH9Z5YQVyM5sPtomUn20JclJr7U6CSPN11UsGH4bTxWB4+10WfxZ2km0L l3sUWtygZrDRQnpAUhO1FM5NXoTUAaqDd5eT3DBJw8yaNvRtwsJ2LqsgbgnYuJPd47cm 0j3d5zD0CUwWP4H5xnL89VlgTZ0zeWyZrrxDi8KRbJ+kmqRjX3o3keFBtYoMIevFXrCc 5W/8w807evySxw79kTpNmgg8yYGZgHbJmgZ78hTC6FN+zQyyFWwMIhCEwxeMOoIoJl5o ig== Received: from aserv0021.oracle.com (aserv0021.oracle.com [141.146.126.233]) by aserp2120.oracle.com with ESMTP id 2nh3mph8um-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 05 Nov 2018 20:08:25 +0000 Received: from userv0121.oracle.com (userv0121.oracle.com [156.151.31.72]) by aserv0021.oracle.com (8.14.4/8.14.4) with ESMTP id wA5K8JrN016131 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 5 Nov 2018 20:08:19 GMT Received: from abhmp0016.oracle.com (abhmp0016.oracle.com [141.146.116.22]) by userv0121.oracle.com (8.14.4/8.13.8) with ESMTP id wA5K8HxW020692; Mon, 5 Nov 2018 20:08:18 GMT Received: from [10.152.33.198] (/10.152.33.198) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Mon, 05 Nov 2018 12:08:17 -0800 Subject: Re: [PATCH 00/10] steal tasks to improve CPU utilization To: Subhra Mazumdar , mingo@redhat.com, peterz@infradead.org Cc: dhaval.giani@oracle.com, daniel.m.jordan@oracle.com, pavel.tatashin@microsoft.com, matt@codeblueprint.co.uk, umgwanakikbuti@gmail.com, riel@redhat.com, jbacik@fb.com, juri.lelli@redhat.com, linux-kernel@vger.kernel.org, valentin.schneider@arm.com, vincent.guittot@linaro.org, quentin.perret@arm.com References: <1540220381-424433-1-git-send-email-steven.sistare@oracle.com> From: Steven Sistare Organization: Oracle Corporation Message-ID: <0ac6a3ec-84af-1868-936c-1ccc0d401af8@oracle.com> Date: Mon, 5 Nov 2018 15:08:16 -0500 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 8bit X-Proofpoint-Virus-Version: vendor=nai engine=5900 definitions=9068 signatures=668683 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 malwarescore=0 phishscore=0 bulkscore=0 spamscore=0 mlxscore=0 mlxlogscore=865 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1807170000 definitions=main-1811050179 Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 11/2/2018 7:39 PM, Subhra Mazumdar wrote: > On 10/22/18 7:59 AM, Steve Sistare wrote: >> When a CPU has no more CFS tasks to run, and idle_balance() fails to >> find a task, then attempt to steal a task from an overloaded CPU in the >> same LLC. Maintain and use a bitmap of overloaded CPUs to efficiently >> identify candidates.  To minimize search time, steal the first migratable >> task that is found when the bitmap is traversed.  For fairness, search >> for migratable tasks on an overloaded CPU in order of next to run. >> >> This simple stealing yields a higher CPU utilization than idle_balance() >> alone, because the search is cheap, so it may be called every time the CPU >> is about to go idle.  idle_balance() does more work because it searches >> widely for the busiest queue, so to limit its CPU consumption, it declines >> to search if the system is too busy.  Simple stealing does not offload the >> globally busiest queue, but it is much better than running nothing at all. >> >> The bitmap of overloaded CPUs is a new type of sparse bitmap, designed to >> reduce cache contention vs the usual bitmap when many threads concurrently >> set, clear, and visit elements. >> > Is the bitmask saving much? I tried a simple stealing that just starts > searching the domain from the current cpu and steals a thread from the > first cpu that has more than one runnable thread. It seems to perform > similar to your patch. > > hackbench on X6-2: 2 sockets * 22 cores * 2 hyperthreads = 88 CPUs >                 baseline        %stdev  patch %stdev > 1(40 tasks)     0.5524          2.36    0.5522 (0.045%) 3.82 > 2(80 tasks)     0.6482          11.4    0.7241 (-11.7%) 20.34 > 4(160 tasks)    0.9756          0.95    0.8276 (15.1%) 5.8 > 8(320 tasks)    1.7699          1.62    1.6655 (5.9%) 1.57 > 16(640 tasks)   3.1018          0.77    2.9858 (3.74%) 1.4 > 32(1280 tasks)  5.565           0.62    5.3388 (4.1%) 0.72 > > X6-2: 2 sockets * 22 cores * 2 hyperthreads = 88 CPUs > Oracle database OLTP, logging _enabled_ > > Users %speedup > 20 1.2 > 40 -0.41 > 60 0.83 > 80 2.37 > 100 1.54 > 120 3.0 > 140 2.24 > 160 1.82 > 180 1.94 > 200 2.23 > 220 1.49 Hi Subhra, The bitset is a few percent faster than iterating over CPUs in the tests I ran on the X6-2 with 44 CPUs per node. If we extend stealing to RT, folks care even more about a few percent. The difference should be greater on systems with more CPUs per socket, and greater if we extend stealing to steal across NUMA nodes, and greater if Valentin adds another bitset for misfits. Lastly, there is no measurable downside in maintaining the overloaded CPUs bitset. I ran experiments where I set and cleared the bits in overload_set and overload_clear, but disabled stealing itself, and saw no significant difference versus the baseline. - Steve