bugs/issue-507685b9ac970ed0fdbc479e4d25fc07ee13efe5.yaml

   1 --- !ditz.rubyforge.org,2008-03-06/issue
   2 title: Refine approach for sharing pointer data structures with compute device
   3 desc: |-
   4   E.g., one approach might be to prepend a bitfield to structures to be passed to
   5   the compute device indicating the positions of pointers in the structure, so
   6   that any necessary dependencies could be included and passed as well.  (The
   7   resulting collection of structures could be packed into a pre-allocated memory
   8   area, a new area could be made, etc., but the primary point is that it would
   9   not be necessary to use a special pointer structure (or pointer macros) on the
  10   host.)
  11
  12   (The above approach would be most appropriate to areas where structural depth
  13   is shallow [i.e., nested dependency counts are small] and structures are small,
  14   reflecting the situation for most of 2D code.  For 3D code, a different
  15   approach might be required (e.g., the current approach of pointer encoding in a
  16   union or structure, a new approach involving a pre-allocated data structure, or
  17   multiple such structures as with a traditional memory page allocator, etc.))
  18 type: :task
  19 component: libale
  20 release: 0.0.0
  21 reporter: David Hilvert <dhilvert@auricle.dyndns.org>
  22 status: :unstarted
  23 disposition:
  24 creation_time: 2009-10-22 16:55:57.695059 Z
  25 references: []
  26
  27 id: 507685b9ac970ed0fdbc479e4d25fc07ee13efe5
  28 log_events:
  29 - - 2009-10-22 16:56:00.206484 Z
  30   - David Hilvert <dhilvert@auricle.dyndns.org>
  31   - created
  32   - ""
  33 - - 2009-10-22 17:07:07.287977 Z
  34   - David Hilvert <dhilvert@auricle.dyndns.org>
  35   - commented
  36   - |-
  37     It's possible that, if done properly, such a reformatting of pointers could
  38     allow processing to more easily occur in client code (e.g., for the case of
  39     parsing of filter and rendering descriptor strings appearing within
  40     command-line arguments, which should really be a client task).
  41
  42     Further, consider that a parameter for type could be used as an alternative to
  43     a bitfield structure member in at least some cases, as such a parameter could
  44     be used for either retrieving information about pointer dependencies from some
  45     other location or for directly representing such a bitfield.
  46 - - 2009-10-22 18:30:23.843635 Z
  47   - David Hilvert <dhilvert@auricle.dyndns.org>
  48   - commented
  49   - |-
  50     Consider that the above-noted bitfields or type signifiers could be specified
  51     explicitly by the user in addition to structure specification, or such
  52     bitfields or signifiers could be extracted automatically from headers (either
  53     .h or, if this is not sufficient, a different representation, such as IDL [see
  54     {issue d0797684fabf05af24e73639e0ce5e30a145a3c5} for links to CORBA pages that might be a relevant starting point for
  55     investigation of IDL as a possibility; this could be seen as a special form of
  56     serialization or remote execution, as alluded to in the earlier bug comments).
  57 - - 2009-10-22 18:41:29.273835 Z
  58   - David Hilvert <dhilvert@auricle.dyndns.org>
  59   - commented
  60   - |-
  61     An alternative to dealing with OpenCL's concept of memory management might be to
  62     use an architecture that allows the compute device to interact with host memory.
  63     (Cell might be one such architecture; Gregory Maxwell had suggested a Cell port
  64     ca. 2007, which inspired these acceleration efforts.  Whether Cell is the most
  65     appropriate target at the moment is not clear, due to issues of availability among
  66     testers.)
  67 - - 2009-10-22 20:33:58.215645 Z
  68   - David Hilvert <dhilvert@auricle.dyndns.org>
  69   - commented
  70   - |-
  71     Note that, if a Cell approach is pursued, an acceptable alternative for testers
  72     not using Cell might be AltiVec or SSE (which had been suggested on the mailing list
  73     or in e-mail some time ago; check the reference).  A review of Wikipedia's AltiVec
  74     article indicates that both of these have instructions for controlling cache, which
  75     is observably a problem in multi-threaded operation (at least) in the multi-alignment
  76     case.
  77
  78     Wikipedia refs:
  79
  80     http://en.wikipedia.org/wiki/AltiVec
  81     http://en.wikipedia.org/wiki/Streaming_SIMD_Extensions
  82     http://en.wikipedia.org/wiki/Cell_software_development
  83     http://en.wikipedia.org/wiki/Cell_(microprocessor)
  84 - - 2009-10-23 11:29:37.802858 Z
  85   - David Hilvert <dhilvert@auricle.dyndns.org>
  86   - commented
  87   - "Consider that it would probably be worthwhile to compare speeds for GPU, Cell,\n\
  88     and so-called multimedia extensions (SSE, etc.), for tasks similar to those\n\
  89     found in ALE 2D and 3D code.\n\n\
  90     Relevant sources may include (via Google cell gpu sse benchmarks):\n\n\
  91     http://ps3hacking.googlecode.com/files/Benchmark-ITA.pdf\n\n\
  92     \twhich compares operations on images, giving \n\n\
  93     \t\t3.3ms CPU\n\
  94     \t\t2.4ms CPU (SIMD)\n\
  95     \t\t1.0ms GPU (8 pixel shaders)\n\
  96     \t\t0.87ms Cell\n\
  97     \t\t0.4ms GPU (32 pixel shaders)\n\n\
  98     \tand which identifies memory transfers as the main bottleneck (which\n\
  99     \tseems consistent with what is observed at least in the multi-alignment\n\
 100     \tcase of ALE, although this latter may be at least partly due to caching\n\
 101     \tinefficiencies).\n\n\
 102     \tThe paper gives a general overview of differences, identifying relevant\n\
 103     \tparameters of the tested configurations for Cell (204.8 GFLOPS, 3.2GHz,\n\
 104     \t25.6GB/s to memory), GeForce 8800 GTX (518.4, 1.35, 86.4), GeForce 7800\n\
 105     \tGTX (165, 0.43, 38.4), GeForce 6800 Ultra (54, 0.4, 35.2).\n\n\
 106     \tSuggested means of using SSE is via an include file apparently provided\n\
 107     \tby Intel (?).\n\n\
 108     \tThe method tested for benchmarking the various hardware is image\n\
 109     \tsegmentation by Laplacian kernel computation.\n\n\
 110     \tAs expected, transfer of images to/from GPU is identified as a\n\
 111     \tsignificant bottleneck in the GPU case, along with context creation\n\
 112     \t(for Cg).\n\n\
 113     \tThe paper explicitly notes its choice of commodity processors,\n\
 114     \tsomething relevant to availibility of hardware to testing communities\n\
 115     \tfor FOSS projects.\n\n\
 116     \tCell is mentioned as being particularly dependent on choice of compiler\n\
 117     \toptions (not a good thing).\n\n\
 118     \tDetails:\n\n\
 119     \tPaper submitted for the First Workshop on General Purpose Processing on\n\
 120     \tGraphics Processing Units, October 4, 2007 Northeastern University,\n\
 121     \tBoston, MA\n\n\
 122     \t\"Benchmark of multi-core technologies through image segmentation\n\
 123     \talgorithms using Cell processor, GPGPU architecture and SIMD\n\
 124     \ttechniques\"\n\n\
 125     \tDaniel L\xC3\xA9lis Baggio (danielbaggio@gmail.com), Fernando Fernandes Neto\n\
 126     \t(alphakiller_@msn.com), Thom\xC3\xA1s Dias (tcdias@gmail.com), Einstein do\n\
 127     \tNascimento Jr.  (einsteinnjr@gmail.com) Mauro Eidi Vilela\n\
 128     \tAssano(massano@br.ibm.com), Celso Hirata (hirata@ita.br) - Instituto\n\
 129     \tTecnol\xC3\xB3gico de Aeron\xC3\xA1utica - Brazil \n\n\
 130     A tentative conclusion might be that it would be unwise to ignore GPUs."
 131 - - 2009-10-23 12:46:31.241173 Z
 132   - David Hilvert <dhilvert@auricle.dyndns.org>
 133   - commented
 134   - "Relevant comparisons for computational hardware would probably include any based on \n\
 135     results from the Folding@home project (since this code would probably be optimized for\n\
 136     the various platforms).\n\n\
 137     Results for this project and others are found through the earlier-referenced Google\n\
 138     search.  Also found are:\n\n\
 139     \thttp://en.wikipedia.org/wiki/Smith-Waterman_algorithm\n\n\
 140     Which indicates that substantial speed-up is possible via SSE2 (Core 2 Duo, in\n\
 141     contrast with the Centrino used in the earlier-referenced paper).\n\n\
 142     Worthwhile would probably be to investigate further what cache management\n\
 143     facilities are available or necessary for efficient SSE programming, as well as\n\
 144     how effectively these are/can be used from within OpenCL. \n\n\
 145     And of possible interest might be: \n\n\
 146     \tSatoshi Matsuoka1, et al.  GPU accelerated computing\xE2\x80\x94from hype to\n\
 147     \tmainstream, the rebirth of vector computing.  SciDAC 2009.  (Which\n\
 148     \twww.iop.org URL Google mangles in a manner inconvenient for\n\
 149     \treproduction here, but the paper is available on-line.)\n\n\
 150     Conclusions, however, are not immediately clear, and not much detail is given\n\
 151     on programming techniques used in the case of CPUs.  Performance increases for\n\
 152     GPUs are emphasized, however, as seems to be fairly typical of what is usually\n\
 153     said of GPUs when these are proposed as a solution for vector problems.\n\n\
 154     One conclusion that might be drawn from the above is that GPUs cannot easily be\n\
 155     ignored (stressing importance of OpenCL), and further that if it is possible to\n\
 156     program CPUs well for efficient caching and memory transfer, doing so is\n\
 157     sufficiently non-trivial that challenges encountered in GPU programming could\n\
 158     not easily justify a focus on CPU (e.g., x86 SSE) techniques (which is\n\
 159     effectively what would occur if a combined Cell and CPU development approach\n\
 160     were pursued, since most testers will not have a Cell in the near- (and likely\n\
 161     also long-) term).\n\n\
 162     A remaining question is whether CPUs could be efficiently used for transferring\n\
 163     data structures from a form encoded in pointer structures to a form encoded in\n\
 164     a manner more easily accessible to GPUs, so that the sorts of problems with\n\
 165     pointer encoding currently seen might be avoided.  For flattening the rather\n\
 166     shallow 2D structures, it seems clear that this is at least possible (with\n\
 167     techniques suggested in this [?] bug record), and it may also be possible in\n\
 168     the case of 3D structures (e.g., if flattening of the octree occurs relative to\n\
 169     a particular perspective).  Perhaps better for 3D would be to collect elements\n\
 170     of the octree into pages, according to memory page allocation techniques\n\
 171     suggested earlier, which would allow reference to locations relative to a page\n\
 172     start; the optimization problem would then be efficient (in speed and source\n\
 173     complexity) manipulation of pages."
 174 - - 2009-10-23 13:08:29.764834 Z
 175   - David Hilvert <dhilvert@auricle.dyndns.org>
 176   - commented
 177   - |-
 178     Given the fact that 3D will have to be addressed, given the fact that the
 179     current arrangement of pointer structures occurs via typedefs and macros, and
 180     given the earlier comments in this bug entry, and the current approach of
 181     separation of allocated device memory into pages, suitable to 3D, consider that
 182     the best approach might simply be to continue with the current pointer encoding
 183     approach, using macros (as is currently done), which should allow for an
 184     efficient transition in the case that hardware and libraries eventually support
 185     sharing of pointers (or at least sharing of pointer-based data structures) in
 186     the most general case (which seems most restricted by the GPU case at the
 187     moment).
 188
 189     How to allow for such data structures to be built on the client side when
 190     appropriate is probably something worth further investigation, but this should
 191     not present a significant challenge.  The more relevant aspect is probably
 192     whether it is desirable (as it might be argued) that things like parsing of
 193     filter descriptor strings are of sufficiently general use that they should
 194     appear in a library (which was in fact the initial motivating factor for
 195     inclusion, prior to considerations of implementation details).
 196 - - 2009-10-23 16:36:42.198652 Z
 197   - David Hilvert <dhilvert@auricle.dyndns.org>
 198   - commented
 199   - "Note that anyone involved in vector processing over complex data structures\n\
 200     must wonder whether it is better to attempt to fit the structures to current\n\
 201     technology or rather work on technology better suited to the data structures.\n\
 202     E.g., a [capable] MMU for GPUs would be rather useful, and apparently\n\
 203     justified, given the resources being directed toward GPGPU and the high prices\n\
 204     associated with better graphics cards and with special-purpose vector\n\
 205     accelerators.\n\n\
 206     Given the extent of overlap that is growing between CPU and GPU manufacturers,\n\
 207     one might imagine that such integration of memory management would be not far\n\
 208     off, but I have seen no discussion of it yet.\n\n\
 209     Searching (Google gpu mmu) indicates that mobile GPUs (at least) have\n\
 210     integrated MMU for transferring data to/from main memory.\n\
 211     http://www.x.org/wiki/ttm indicates that GPU memory maps (as opposed to mapping\n\
 212     for CPU user space) are left to drivers, which raises the question of whether\n\
 213     limitations in OpenCL are strictly a software issue.  The section \"AGP TTM\n\
 214     backend\" particularly gives this impression w.r.t. the i965.\n\n\
 215     http://en.wikipedia.org/wiki/CUDA appears to suggest that interaction with host\n\
 216     memory may be straightforward in CUDA (\"Scattered reads \xE2\x80\x93 code can read from\n\
 217     arbitrary addresses in memory.\"; but we must wonder whether the memory in\n\
 218     question includes host memory, or whether explicit transfers between host and\n\
 219     device domains are necessary).  Examples on the same page suggest that this is\n\
 220     not the case, however (indeed, explicit transfers appear to be required).\n\n\
 221     The above seems to suggest that the technology in need of work might be a\n\
 222     software technology in the case of hardware with open specifications (such as\n\
 223     Intel's integrated chips), and that work is progressing in the general area of\n\
 224     drivers in the Linux and Xorg driver space, suggesting that providing a user\n\
 225     API might be what is necessary.  The next step would probably be to investigate\n\
 226     the hardware or driver facilities further (e.g., via Linux or Xorg\n\
 227     documentation and source, or via hardware specs)."
 228 - - 2009-10-23 17:21:15.507335 Z
 229   - David Hilvert <dhilvert@auricle.dyndns.org>
 230   - commented
 231   - |-
 232     Consider that a reasonable approach to the previously-mentioned use of hardware
 233     mapping via Linux (or Xorg) drivers might be to provide a map that can be used
 234     during execution of an OpenCL kernel.  Exactly how to negotiate the map between
 235     user space and the OpenCL framework might be tricky, however.  One might
 236     imagine use of OpenCL extensions (either in the usual sense or otherwise), but
 237     note that there's no obvious way to integrate an extension into an arbitrary
 238     given OpenCL implementation.  Still, this approach would probably be worth
 239     looking at.
 240
 241     To wit, there's the advantage of avoiding maintaining maps in user code (common
 242     to hardware map solutions), and hence avoiding the need to explicitly transfer
 243     maps from user code to the device; further, there's the advantage of using
 244     OpenCL, which, aside from the awkwardness of the call interface and absence of
 245     provisions for pointer sharing, appears to be better than most alternatives, in
 246     generality if nothing else.
 247 - - 2009-10-23 18:42:59.183941 Z
 248   - David Hilvert <dhilvert@auricle.dyndns.org>
 249   - commented
 250   - |-
 251     Consider that a reasonable sort of OpenCL extension (or a reasonable mode of
 252     operation, to frame the idea outside of the specific realm of OpenCL) would be
 253     to share an identical mapping (i.e., identical pointer values) of all data
 254     shared with the GPU between GPU and user-space CPU memory maps.
 255
 256     A reasonable restriction might be that GPU and CPU code must have the same
 257     pointer size, but this does not seem to be a serious restriction.  (In the case
 258     of a 64-bit GPU, it would not be difficult to find a 64-bit host, and in the
 259     case of a 32-bit GPU, 32-bit code could be executed on the host.  In the case
 260     of smaller pointer sizes, it should be possible to use appropriate masks, but
 261     this last case probably won't be very common.)
 262 git_branch: