From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 3069AA0032; Tue, 13 Sep 2022 16:56:32 +0200 (CEST) Received: from [217.70.189.124] (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id BD29D4021D; Tue, 13 Sep 2022 16:56:31 +0200 (CEST) Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by mails.dpdk.org (Postfix) with ESMTP id BA26340151 for ; Tue, 13 Sep 2022 16:56:29 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1663080989; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=FRmor10lido36blFx2Vk1vnjvMXxZnSkXP77DpxMH4o=; b=SqQt4/VDbEEJdmbwEJeGKe8binDxRkv928NpkvUb0D42SPgjRe/iCQAPNaCqqkaYd3ICzc qyN+buFU1VEkQOH85+QylXWujTRH4GKHIzJLzJHek9zikHTG6TkVVG+eFT+jHiXPuFOgVn wvzrj6YlGK2hx1bJTiFVNsytOHMjUf4= Received: from mail-lf1-f70.google.com (mail-lf1-f70.google.com [209.85.167.70]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-205-9kNJzO1ZONa0s882voixfQ-1; Tue, 13 Sep 2022 10:56:28 -0400 X-MC-Unique: 9kNJzO1ZONa0s882voixfQ-1 Received: by mail-lf1-f70.google.com with SMTP id y22-20020a199156000000b00498f587546cso3970930lfj.14 for ; Tue, 13 Sep 2022 07:56:27 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date; bh=FRmor10lido36blFx2Vk1vnjvMXxZnSkXP77DpxMH4o=; b=E5IxxNiGsKWaLBpnLyitHUM6GMy1O89m2WQ6GgrIBb95EAHcNrgHuG37T9ttCWmXEC 11altC04w1815Un9m2M4Qsh/3eTKyetodIvPI2gJmab+ckj7H/uzmFw8nncsKYzIfvIj P1KZgYsSdho1l6S1FQGcMr2Xlcdg0BbtNu5FwgSFzNPakyXvhADjZcYS/8uEm+szBG58 kNxKEvfVZ17DSia83dSyXTeJyOstWsnimqUkqYKyR7gyqJNip3bq0K2xmVo3ubmtfx5M z/7Skoj193hRJZp+oQTn80xWmFIQ/yV/xl12ivDexdDi1fUiTMJ8lLFT6tT6GnfO4vvn C6dQ== X-Gm-Message-State: ACgBeo07DpvJkdgJts2GH3BoQupZJH4iFk4nSBfZBx1xDFrPy/f1LNiw Sdul+RjM+pZ+0TtPhldAdX/URTZnwWGdtjoGhd0akozoMaO7voR9qAf+gCIq7To6RWoggCg7a/i Mhn7BxNl/mPGh0OWjRMw= X-Received: by 2002:a2e:b817:0:b0:26b:e84b:4d80 with SMTP id u23-20020a2eb817000000b0026be84b4d80mr5932565ljo.55.1663080986522; Tue, 13 Sep 2022 07:56:26 -0700 (PDT) X-Google-Smtp-Source: AA6agR79Yd2Z7MyJ5ssJdXQd4LyEz6IbQz14eziT5+yQIjgjVJ5RSO9x9S0SBdyJtymxMWuCH8yHvcSW1qV4tq9vID8= X-Received: by 2002:a2e:b817:0:b0:26b:e84b:4d80 with SMTP id u23-20020a2eb817000000b0026be84b4d80mr5932554ljo.55.1663080986269; Tue, 13 Sep 2022 07:56:26 -0700 (PDT) MIME-Version: 1.0 References: <20220810074518.1695013-1-leyi.rong@intel.com> <20220831064639.4163765-1-leyi.rong@intel.com> <20220831064639.4163765-2-leyi.rong@intel.com> In-Reply-To: <20220831064639.4163765-2-leyi.rong@intel.com> From: David Marchand Date: Tue, 13 Sep 2022 16:56:15 +0200 Message-ID: Subject: Re: [PATCH v2 1/2] member: implement NitroSketch mode To: Leyi Rong Cc: ferruh.yigit@xilinx.com, suanmingm@nvidia.com, yipeng1.wang@intel.com, zaoxingliu@gmail.com, sameh.gobriel@intel.com, dev@dpdk.org, Bruce Richardson , Aaron Conole , Michael Santana , Lincoln Lavoie X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset="UTF-8" X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org On Wed, Aug 31, 2022 at 8:47 AM Leyi Rong wrote: > > Sketching algorithm provide high-fidelity approximate measurements and > appears as a promising alternative to traditional approaches such as > packet sampling. > > NitroSketch [1] is a software sketching framework that optimizes > performance, provides accuracy guarantees, and supports a variety of > sketches. > > This commit adds a new data structure called sketch into > membership library. This new data structure is an efficient > way to profile the traffic for heavy hitters. Also use min-heap > structure to maintain the top-k flow keys. http://mails.dpdk.org/archives/test-report/2022-August/304026.html This patch adds new symbols in the API without going through the experimental phase. What is the rationale for skipping it? > > [1] Zaoxing Liu, Ran Ben-Basat, Gil Einziger, Yaron Kassner, Vladimir > Braverman, Roy Friedman, Vyas Sekar, "NitroSketch: Robust and General > Sketch-based Monitoring in Software Switches", in ACM SIGCOMM 2019. > https://dl.acm.org/doi/pdf/10.1145/3341302.3342076 > > Signed-off-by: Alan Liu > Signed-off-by: Yipeng Wang > Signed-off-by: Leyi Rong > --- > lib/member/meson.build | 38 +- > lib/member/rte_member.c | 75 ++++ > lib/member/rte_member.h | 151 ++++++- > lib/member/rte_member_heap.h | 424 ++++++++++++++++++ > lib/member/rte_member_sketch.c | 594 ++++++++++++++++++++++++++ > lib/member/rte_member_sketch.h | 97 +++++ > lib/member/rte_member_sketch_avx512.c | 69 +++ > lib/member/rte_member_sketch_avx512.h | 36 ++ > lib/member/rte_xxh64_avx512.h | 117 +++++ > lib/member/version.map | 3 + > 10 files changed, 1600 insertions(+), 4 deletions(-) > create mode 100644 lib/member/rte_member_heap.h > create mode 100644 lib/member/rte_member_sketch.c > create mode 100644 lib/member/rte_member_sketch.h > create mode 100644 lib/member/rte_member_sketch_avx512.c > create mode 100644 lib/member/rte_member_sketch_avx512.h > create mode 100644 lib/member/rte_xxh64_avx512.h > > diff --git a/lib/member/meson.build b/lib/member/meson.build > index e06fddc240..9b3418c25c 100644 > --- a/lib/member/meson.build > +++ b/lib/member/meson.build > @@ -7,6 +7,42 @@ if is_windows > subdir_done() > endif > > -sources = files('rte_member.c', 'rte_member_ht.c', 'rte_member_vbf.c') > +sources = files('rte_member.c', 'rte_member_ht.c', 'rte_member_vbf.c', 'rte_member_sketch.c') > headers = files('rte_member.h') > deps += ['hash'] > +includes += include_directories('../hash', '../ring') > + > +# compile AVX512 version if: > +# we are building 64-bit binary AND binutils can generate proper code > +if dpdk_conf.has('RTE_ARCH_X86_64') and binutils_ok > + # compile AVX512 version if either: > + # a. we have AVX512 supported in minimum instruction set > + # baseline > + # b. it's not minimum instruction set, but supported by > + # compiler > + # > + # in former case, just add avx512 C file to files list > + # in latter case, compile c file to static lib, using correct > + # compiler flags, and then have the .o file from static lib > + # linked into main lib. > + sketch_avx512_cpu_support = ( > + cc.get_define('__AVX512F__', args: machine_args) != '' > + ) > + > + if sketch_avx512_cpu_support == true > + cflags += ['-DCC_AVX512_SUPPORT'] > + if cc.has_multi_arguments('-mavx512f', '-mavx512dq', '-mavx512ifma') > + cflags += ['-mavx512f', '-mavx512dq', '-mavx512ifma'] Pushing those flags in the cflags is probably wrong, as the rest of the library objects will be compiled with those AVX512 flags. If later this library code is run on a non supporting AVX512 system, it will trigger a runtime error. Please look at how other libraries integrated AVX512. Thanks. -- David Marchand